PARTE TERZA: Code di Priorità

15/10/03:
La struttura dati heap binario. Proprietà di ordinamento parziale. Procedure di mantenimento dell'heap: HEAPIFY e BUILD HEAP. Correttezza ed analisi della complessità computazionale.
Dispense: 35, 36, 37, 38, 39, 40.

 
16/10/03:
Algoritmo HEAP SORT. Esemplificazione del suo funzionamento. Analisi della complessità computazionale. Confronto con il MERGE SORT.
Approfondimento: Modifica della procedura HEAPIFY da ricorsiva ad iterativa, al fine di gestire incrementi di una chiave dell'heap.
Dispense: 41, 42.

 
21/10/03:
Coda di priorità e relative operazioni. Gestione di una coda di priorità mediante una lista ordinata o non ordinata. Gestione di una coda di priorità mediante un vettore ordinato e non ordinato. Gestione di una coda di priorità mediante un heap binario con complessità O(log n). Approfondimento: Operazione Delete(S,x) in un heap binario. 
Dispense: 42, 43, 44, 45, 46, 47, 48.