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.