0Pricing
Java Academy · Lezione

PriorityQueue per l'elaborazione ordinata

Utilizzi PriorityQueue con l'ordinamento naturale e comparatori personalizzati in scenari di pianificazione delle attività.

PriorityQueue per l'elaborazione ordinata è una lezione Java Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Java Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Java Academy include 4 lezioni in totale.

Che cos'è una PriorityQueue?

Una PriorityQueue è un min-heap per impostazione predefinita: l'elemento con l'ordinamento naturale più basso si trova sempre in testa. Gli elementi non sono ordinati internamente: solo il minimo è garantito in prima posizione.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (min)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

Struttura interna dell'heap

PriorityQueue utilizza un min-heap binario memorizzato in un array. Il padre all'indice i è sempre ≤ dei figli agli indici 2i+1 e 2i+2. Questo garantisce offer/poll in O(log n) e peek in O(1).

Max-heap con comparatore inverso

Per creare un max-heap (con l'elemento più grande in prima posizione), passi Comparator.reverseOrder():

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(50);
maxPQ.offer(30);

System.out.println(maxPQ.poll()); // 50 (max)
System.out.println(maxPQ.poll()); // 30

PriorityQueue con oggetti personalizzati

Utilizzi un comparatore per ordinare record o classi personalizzati:

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority) // ascending priority
);
queue.offer(new Job("Backup", 5));
queue.offer(new Job("Alert", 1));
queue.offer(new Job("Report", 3));

System.out.println(queue.poll().name()); // Alert (priority 1)

Peek e poll a confronto

peek() restituisce l'elemento in testa senza rimuoverlo. poll() lo rimuove e lo restituisce. Entrambi restituiscono null quando la coda è vuota (a differenza di element()/remove(), che generano un'eccezione).

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("banana");
pq.offer("apple");

System.out.println(pq.peek()); // apple (not removed)
System.out.println(pq.peek()); // apple (still there)
System.out.println(pq.poll()); // apple (removed)
System.out.println(pq.peek()); // banana

Esempio di pianificazione delle attività

PriorityQueue è ideale per le simulazioni di pianificazione della CPU in cui le attività hanno priorità diverse:

record Task(String name, int priority) {}

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
scheduler.offer(new Task("Low", 1));
scheduler.offer(new Task("Critical", 10));
scheduler.offer(new Task("Normal", 5));

while (!scheduler.isEmpty()) {
    System.out.println("Processing: " + scheduler.poll().name());
}
// Critical, Normal, Low

I K elementi più piccoli

PriorityQueue è uno strumento classico per trovare i K elementi più piccoli senza ordinare completamente l'array:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) pq.offer(n);

for (int i = 0; i < k; i++) {
    System.out.print(pq.poll() + " ");
}
// 1 2 3

I K elementi più grandi con un max-heap

In alternativa, durante l'iterazione mantenga un min-heap di dimensione K per trovare i K elementi più grandi:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
// minHeap now contains the 3 largest: [7, 8, 9]
System.out.println(minHeap); // order may vary

Schema dell'algoritmo di Dijkstra

L'algoritmo del cammino minimo di Dijkstra si basa su un min-heap per espandere sempre per primo il nodo non visitato con il costo più basso:

record Entry(int node, int cost) {}

PriorityQueue<Entry> pq = new PriorityQueue<>(
    Comparator.comparingInt(Entry::cost)
);
pq.offer(new Entry(0, 0)); // start node, cost 0

while (!pq.isEmpty()) {
    Entry curr = pq.poll();
    System.out.println("Visit node " + curr.node() + " cost=" + curr.cost());
    // expand neighbors...
}

L'iterazione non è ordinata

L'iterazione su una PriorityQueue NON restituisce gli elementi in ordine di priorità: solo poll() lo fa. Per ottenere un output ordinato, esegua ripetutamente poll invece di usare un ciclo for-each.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,3,1,4,2));

// WRONG for sorted output:
for (int n : pq) System.out.print(n+" "); // unordered!

// CORRECT:
while (!pq.isEmpty()) System.out.print(pq.poll()+" "); // 1 2 3 4 5

Riepilogo delle prestazioni

Complessità delle operazioni di PriorityQueue:

  • offer(e): O(log n)
  • poll(): O(log n)
  • peek(): O(1)
  • contains(e): O(n)
  • remove(e): O(n)

Non è thread-safe: utilizzi PriorityBlockingQueue per l'accesso concorrente.

Verifica rapida

Che cosa garantisce riguardo all'ordine degli elementi l'iterazione su una PriorityQueue con un ciclo for-each?

Riepilogo: PriorityQueue

Punti chiave:

  • PriorityQueue è un min-heap: l'elemento più piccolo viene estratto per primo
  • Utilizzi Comparator.reverseOrder() per un max-heap
  • offer/poll in O(log n), peek in O(1)
  • Casi d'uso classici: K-esimo elemento più grande/più piccolo, Dijkstra, pianificazione delle attività
  • Il ciclo for-each non restituisce gli elementi in ordine di priorità: utilizzi poll()

Domande Frequenti

La lezione «PriorityQueue per l'elaborazione ordinata» è gratuita?

Sì — il testo completo di «PriorityQueue per l'elaborazione ordinata» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Java Academy, passa a CoddyKit PRO. Il corso Java Academy include 4 lezioni in totale.

Cosa imparerò in «PriorityQueue per l'elaborazione ordinata»?

Utilizzi PriorityQueue con l'ordinamento naturale e comparatori personalizzati in scenari di pianificazione delle attività. Eserciti Java Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Java Academy?

Non è richiesta alcuna esperienza precedente. Java Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «PriorityQueue per l'elaborazione ordinata»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Java Academy?

Sì. Ogni lezione Java Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Internals di LinkedList
  2. Operazioni su Deque: stack e queue
  3. LinkedList e ArrayList a confronto
  4. PriorityQueue per l'elaborazione ordinata
← Torna a Java Academy