Java PriorityQueue

PriorityQueue<E> è l'heap del JDK. È una Queue, ma invece del FIFO la testa è sempre l'elemento minimo secondo un Comparator (oppure l'ordine naturale se non ne viene fornito uno). offer è O(log n), poll e peek dalla testa sono rispettivamente O(log n) e O(1), e lo storage sottostante è un array piatto — nessuna allocazione di nodi per elemento. Questo la rende lo strumento giusto per problemi di tipo scheduler: "lavora sempre su ciò che è più urgente in questo momento."

Cosa significa "testa" in questo contesto

Per una coda FIFO, la testa è chi è arrivato per primo. Per una PriorityQueue, la testa è chi ha il valore più piccolo in quel momento — non il più piccolo al momento dell'inserimento:

• peek() restituisce il minimo corrente.
• poll() rimuove il minimo corrente e ribilancia; il successivo peek mostra il nuovo minimo.
• offer(x) inserisce e ribilancia; se x è il nuovo minimo, il successivo peek lo restituisce.

"Minimo" è determinato da:

1. Il Comparator passato al costruttore, se presente.
2. Altrimenti, l'ordine naturale dell'elemento tramite Comparable. Se gli elementi non sono Comparable e non è stato passato un Comparator, la prima chiamata che necessita di un confronto lancia ClassCastException.

Non esiste una modalità max-heap. Se vuoi un max-heap, passa Comparator.reverseOrder() (o il tuo comparatore personalizzato invertito) — questo è l'idioma standard e lo usiamo nell'esempio qui sotto.

Costruirne una

// Natural order (Comparable elements).
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Reversed for max-heap behaviour.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator — by length, then alphabetically.
PriorityQueue<String> byLen = new PriorityQueue<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

// Pre-sized + comparator (initial capacity must come first).
PriorityQueue<String> bigByLen = new PriorityQueue<>(1_000,
    Comparator.comparingInt(String::length));

// From an existing collection.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));

Il costruttore con un singolo argomento che accetta una Collection è O(n) — esegue l'heapify in blocco invece di n offer in O(log n). Utile quando hai già tutti i dati a disposizione.

L'iterazione NON segue l'ordine di priorità

Questa è la sorpresa che coglie la maggior parte delle persone la prima volta. Iterare una PriorityQueue percorre l'array heap sottostante nell'ordine in cui l'heap memorizza i suoi nodi — non in ordine ascendente:

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));
System.out.println(pq);                // possibly [10, 20, 30, 40]
for (int x : pq) System.out.print(x + " "); // possibly: 10 20 30 40
                                            // possibly: 10 40 30 20

L'ordine di stampa è un dettaglio di implementazione del layout dell'heap. Se vuoi gli elementi in ordine di priorità, devi svuotare la coda:

while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // sorted

Tienilo presente quando usi forEach, stream, toArray, o stampi semplicemente la coda per il debug. Lo Stream restituito da stream() non è ordinato, e aggiungere .sorted() richiede che gli elementi siano Comparable (oppure puoi passare un comparatore).

Mutare un elemento dopo offer rompe l'heap

La priorità viene calcolata al momento dell'inserimento. Se inserisci un elemento e poi muti il campo su cui si basa il comparatore, l'heap è ora in uno stato non valido — poll potrebbe restituire la testa sbagliata, contains potrebbe fallire, si perde l'invariante. Non esiste un metodo update o decrease-key.

Le due soluzioni alternative:

• Usa elementi immutabili — record con campi di priorità, o record wrapper come record Task(int priority, String name) {}. Così non c'è nulla da mutare dopo l'inserimento.
• Rimuovi e reinserisci se hai davvero bisogno di cambiare la priorità: pq.remove(task) è O(n) (effettua una ricerca), poi pq.offer(taskWithNewPriority) è O(log n).

Per una coda piccola, rimuovere-e-reinserire va bene. Per "sto riscrivendo l'algoritmo di Dijkstra e ho bisogno di un decrease-key veloce," una PriorityQueue non è lo strumento giusto — occorre un heap indicizzato o un TreeSet di coppie (priority, node).

null e thread safety

Stesse regole del resto di Queue:

• Nessun null. pq.offer(null) lancia NullPointerException.
• Non thread-safe. L'accesso concorrente richiede PriorityBlockingQueue, il cugino in java.util.concurrent.

Un esempio pratico: un piccolo scheduler di task

Il programma seguente usa una PriorityQueue per schedulare task in base alla priorità (numero più basso = più urgente). Mostra anche l'idioma del max-heap e la sorpresa sull'ordine di iterazione.

Interpretando l'esecuzione:

• toString() e forEach hanno mostrato i task in un qualche ordine — non ordinato. Non usarli per il debug di "la priorità è corretta?" — svuota con poll per vedere l'ordine reale.
• Il costruttore bulk ha prodotto un heap correttamente ordinato in una sola operazione — questo è il percorso di heapify in tempo lineare.
• Il blocco di mutazione alla fine è il punto critico in forma concentrata. Abbiamo mutato la priorità dell'array dopo averlo inserito, l'heap non ha avuto la possibilità di ribilanciarsi, e ora peek mente. La soluzione è usare un wrapper immutabile oppure fare remove-e-offer dopo la modifica.

Cosa c'è dopo

Il prossimo capitolo tratta l'implementazione a cui ricorrere quando vuoi una coda FIFO o uno stack o una deque — e quella verso cui il Javadoc del JDK ti spinge come default per tutte e tre: ArrayDeque. È la classe che fa la maggior parte del lavoro dietro le quinte nel codice di esempio dei due capitoli precedenti.

Pratica