PRIORITY QUEUE
Schema della sezione
-
Lezione 14: 29/10/25
- Definizione di Priority Queue; Interfacce Entry(K,V) e PriorityQueue(K,V); applicazioni reali.
Lezione 15: 04/11/25
- Implementazione di una Priority Queue tramite liste (ordinate e non).
- Heap: definizione; proprietà; realizzazione tramite array (level numbering).
- Esercizi: relazione tra array ordinato e heap; esercizio R-9.15 del testo.
Lezione 16: 05/11/25- Implementazione di min e insert tramite heap su array (pseudocodice e analisi).
- Implementazione di removeMin tramite heap su array (pseudocodice e analisi).
- Construzione di uno Heap a partire da un array P di n entry: approccio top-down (pseudocodice e analisi)
Lezione 17: 06/11/25- Construzione di uno Heap a partire da un array P di n entry: approccio bottom-up (pseudocodice e analisi).
- pqSort: SelectionSort, InsertionSort, HeapSort come casi particolari.
- Implementazione in-place di HeapSort
Lezione 18: 11/11/24- Esercizi: esercizio dalla Slide 58, algoritmi Top(S,tau) (dalle Slide 7,8, e 74), removeEntry(P,ell) (dalla Slide 59), Print (T,i,k) (dalla Slide 68 - esercizio C-9.34 di [GTG14]).
Lezione 19: 12/11/25- Implementazione delle Priority Queue in Java: classe PriorityQueue<E>
Materiale:
- Slide sulle Priority Queue (v. 06/11/25)
- Slide di Esercizi sulle Priority Queue (v. 11/11/25)
- Esercizi svolti sulle Priority Queue (v. 21/11/25)
- Libro di testo [GTG14]: Ch. 9 (Par. 9.1-9.4).
- Esercizi consigliati dal libro di testo: R-9.1; R-9.9: R-9.10; R-9.12; R-9.13; R-9.15; R-9.16; R-9.17; R-9.18; R-9.19; R-9.23; C-9.30; C-9.32; C-9.34; C-9.36; C-9.37; C-9.38; C-9.39.