0Pricing
Java Academy · Lektion

PriorityQueue für geordnete Verarbeitung

Verwenden Sie PriorityQueue mit natürlicher Ordnung und eigenen Comparatoren für Szenarien der Aufgabenplanung.

PriorityQueue für geordnete Verarbeitung ist eine kostenlose Java Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Java Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Was ist eine PriorityQueue?

Eine PriorityQueue ist standardmäßig ein Min-Heap: Das Element mit dem kleinsten Wert gemäß der natürlichen Ordnung befindet sich immer am Kopf. Die Elemente sind intern nicht sortiert – nur das Minimum ist an erster Stelle garantiert.

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

Interne Heap-Struktur

PriorityQueue verwendet einen binären Min-Heap, der in einem Array gespeichert wird. Das Elternelement am Index i ist immer ≤ den Kindelementen an den Indizes 2i+1 und 2i+2. Dadurch sind offer und poll in O(log n) sowie peek in O(1) möglich.

Max-Heap mit umgekehrtem Comparator

Um einen Max-Heap zu erstellen, bei dem das größte Element zuerst kommt, übergeben Sie 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 mit benutzerdefinierten Objekten

Verwenden Sie einen Comparator, um benutzerdefinierte Datensätze oder Klassen zu ordnen:

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 vs. Poll

peek() gibt das Kopfelement zurück, ohne es zu entfernen. poll() entfernt es und gibt es zurück. Beide geben bei einer leeren Warteschlange null zurück (im Gegensatz zu element()/remove(), die eine Ausnahme auslösen).

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

Beispiel zur Aufgabenplanung

PriorityQueue eignet sich ideal für Simulationen der CPU-Aufgabenplanung, bei denen Aufgaben unterschiedliche Prioritäten haben:

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

K kleinste Elemente

PriorityQueue ist ein klassisches Werkzeug, um die K kleinsten Elemente zu finden, ohne das Array vollständig zu sortieren:

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

K größte Elemente mit einem Max-Heap

Alternativ können Sie beim Durchlaufen einen Min-Heap der Größe K verwalten, um die K größten Elemente zu finden:

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

Muster des Dijkstra-Algorithmus

Dijkstras Algorithmus für kürzeste Wege verwendet einen Min-Heap, um immer zuerst den günstigsten noch nicht besuchten Knoten zu erweitern:

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...
}

Die Iteration ist ungeordnet

Das Iterieren über eine PriorityQueue gibt die Elemente NICHT in Prioritätsreihenfolge zurück – nur poll() tut dies. Für eine sortierte Ausgabe rufen Sie wiederholt poll auf, statt eine for-each-Schleife zu verwenden.

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

Zusammenfassung der Performance

Komplexität der PriorityQueue-Operationen:

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

Nicht threadsicher – verwenden Sie für den gleichzeitigen Zugriff PriorityBlockingQueue.

Kurzer Test

Welche Garantie bezüglich der Reihenfolge der Elemente gibt es, wenn Sie eine PriorityQueue mit einer for-each-Schleife durchlaufen?

Zusammenfassung: PriorityQueue

Wichtigste Erkenntnisse:

  • PriorityQueue ist ein Min-Heap: Das kleinste Element wird zuerst mit poll abgerufen
  • Verwenden Sie Comparator.reverseOrder() für einen Max-Heap
  • offer und poll in O(log n), peek in O(1)
  • Klassische Anwendungsfälle: K-größtes/kleinstes Element, Dijkstra, Aufgabenplanung
  • for-each liefert keine Prioritätsreihenfolge – verwenden Sie poll()

Häufig gestellte Fragen

Ist die Lektion „PriorityQueue für geordnete Verarbeitung“ kostenlos?

Ja — der vollständige Text von „PriorityQueue für geordnete Verarbeitung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Java Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „PriorityQueue für geordnete Verarbeitung“?

Verwenden Sie PriorityQueue mit natürlicher Ordnung und eigenen Comparatoren für Szenarien der Aufgabenplanung. Du übst Java Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Java Academy zu starten?

Keine Vorkenntnisse erforderlich. Java Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.

Wie lange dauert die Lektion „PriorityQueue für geordnete Verarbeitung“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Java Academy-Lektion Code schreiben und ausführen?

Ja. Jede Java Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Interna von LinkedList
  2. Deque-Operationen: Stack und Queue
  3. LinkedList vs. ArrayList: Abwägungen
  4. PriorityQueue für geordnete Verarbeitung
← Zurück zu Java Academy