Java PriorityQueue-Klasse | W3Docs Learn Java

PriorityQueue<E> ist der Heap des JDK. Es ist eine Queue, aber statt FIFO ist der Kopf immer das kleinste Element gemäß einem Comparator (oder der natürlichen Reihenfolge, wenn keiner angegeben wurde). offer ist O(log n), poll und peek am Kopf sind jeweils O(log n) und O(1), und der zugrundeliegende Speicher ist ein flaches Array — keine Knotenallokierung pro Element. Das macht sie zum richtigen Werkzeug für Scheduler-ähnliche Probleme: „Arbeite immer an dem, was als Nächstes am dringendsten ist."

Was „Kopf" hier bedeutet

Bei einer FIFO-Warteschlange ist der Kopf derjenige, der zuerst ankam. Bei einer PriorityQueue ist der Kopf derjenige mit dem kleinsten Wert zu diesem Zeitpunkt — nicht der kleinste zum Einfügezeitpunkt:

peek() gibt das aktuelle Minimum zurück.
poll() entfernt das aktuelle Minimum und balanciert neu; das nächste peek zeigt das neue Minimum.
offer(x) fügt ein und balanciert neu; wenn x das neue Minimum ist, gibt das nächste peek es zurück.

„Kleinstes" wird bestimmt durch:

Den Comparator, der dem Konstruktor übergeben wurde, falls vorhanden.
Andernfalls die natürliche Reihenfolge des Elements über Comparable. Wenn die Elemente nicht Comparable sind und kein Comparator übergeben wurde, wirft der erste Vergleichsaufruf eine ClassCastException.

Es gibt keinen Maximalhaufen-Modus. Wenn ein Max-Heap gewünscht wird, übergib Comparator.reverseOrder() (oder den benutzerdefinierten Comparator umgekehrt) — das ist das Standardidiom und wird im folgenden Beispiel verwendet.

Einen erstellen

// 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));

Der Einzelargument-Konstruktor, der eine Collection entgegennimmt, ist O(n) — er heapifiziert in einem Schritt statt n O(log n)-offers. Nützlich, wenn alle Daten bereits vorhanden sind.

Iteration erfolgt NICHT in Prioritätsreihenfolge

Das ist die Überraschung, die die meisten Menschen einmal erlebt. Das Iterieren über eine PriorityQueue durchläuft das zugrundeliegende Heap-Array in der Reihenfolge, in der der Heap seine Knoten zufällig speichert — nicht in aufsteigender Reihenfolge:

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

Die Druckreihenfolge ist ein Implementierungsdetail des Heap-Layouts. Um Elemente in Prioritätsreihenfolge zu erhalten, muss der Inhalt geleert werden:

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

Beachte dies bei forEach, stream, toArray oder wenn die Warteschlange zum Debuggen ausgegeben wird. Der von stream() zurückgegebene Stream ist nicht sortiert, und das Hinzufügen von .sorted() erfordert, dass die Elemente Comparable sind (oder es kann ein Comparator übergeben werden).

Das Mutieren eines Elements nach `offer` bricht den Heap

Die Priorität wird zum Zeitpunkt der Einfügung berechnet. Wenn ein Element eingefügt und danach das Feld, auf das der Comparator schaut, mutiert wird, ist der Heap in einem ungültigen Zustand — poll kann den falschen Kopf zurückgeben, contains kann verfehlen, die Invariante geht verloren. Es gibt keine update- oder decrease-key-Methode.

Die beiden Workarounds:

Unveränderliche Elemente verwenden — Records mit Prioritätsfeldern oder Wrapper-Records wie record Task(int priority, String name) {}. Dann gibt es nach dem Einfügen nichts zu mutieren.
Entfernen und neu einfügen, wenn die Priorität wirklich geändert werden muss: pq.remove(task) ist O(n) (es sucht), dann ist pq.offer(taskWithNewPriority) O(log n).

Für eine kleine Warteschlange ist das Entfernen und erneute Einfügen in Ordnung. Für „Ich schreibe Dijkstras Algorithmus neu und brauche schnelles decrease-key" ist eine PriorityQueue nicht das richtige Werkzeug — dann braucht man einen indizierten Heap oder ein TreeSet aus (priority, node)-Paaren.

`null` und Thread-Sicherheit

Gleiche Regeln wie beim Rest von Queue:

Keine Nulls. pq.offer(null) wirft NullPointerException.
Nicht thread-sicher. Gleichzeitiger Zugriff benötigt PriorityBlockingQueue, den Cousin aus java.util.concurrent.

Ein Praxisbeispiel: ein kleiner Task-Scheduler

Das folgende Programm verwendet eine PriorityQueue, um Aufgaben nach Priorität zu planen (niedrigere Zahl = dringender). Es zeigt auch das Max-Heap-Idiom und die Überraschung bei der Iterationsreihenfolge.

java— editable, runs on the server

import java.util.*;

public class TaskScheduler {
  record Task(int priority, String name) {
    @Override public String toString() { return name + "(" + priority + ")"; }
  }

public static void main(String[] args) {
    // Min-heap by priority field.
    PriorityQueue<Task> queue = new PriorityQueue<>(
        Comparator.comparingInt(Task::priority));

queue.offer(new Task(5, "send-newsletter"));
    queue.offer(new Task(1, "page-on-call"));
    queue.offer(new Task(3, "retry-webhook"));
    queue.offer(new Task(2, "flush-buffer"));
    queue.offer(new Task(4, "compact-logs"));

System.out.println("queue (toString — not in priority order!):");
    System.out.println("  " + queue);

System.out.println("\nfor-each iteration order — also not sorted:");
    queue.forEach(t -> System.out.println("  " + t));

System.out.println("\npolling in priority order:");
    while (!queue.isEmpty()) System.out.println("  next: " + queue.poll());

// --- Max-heap: just reverse the comparator ---
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int n : new int[]{ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 }) maxHeap.offer(n);
    System.out.print("\nmax-heap drain: ");
    while (!maxHeap.isEmpty()) System.out.print(maxHeap.poll() + " ");
    System.out.println();

// --- Bulk constructor — O(n) heapify ---
    PriorityQueue<Integer> bulk = new PriorityQueue<>(List.of(40, 10, 30, 20, 50));
    System.out.print("bulk-built drain: ");
    while (!bulk.isEmpty()) System.out.print(bulk.poll() + " ");
    System.out.println();

// --- Mutation footgun ---
    PriorityQueue<int[]> mutable = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    int[] urgent = { 1, 42 };
    int[] later  = { 9, 99 };
    mutable.offer(urgent);
    mutable.offer(later);
    System.out.println("\nbefore mutate: head=" + Arrays.toString(mutable.peek()));
    urgent[0] = 100;   // change priority of an already-inserted element
    System.out.println("after mutate:  head=" + Arrays.toString(mutable.peek())
        + "  ← heap invariant is now broken; poll order is unreliable");
  }
}

Die Ausgabe lesen:

toString() und forEach zeigten die Aufgaben in irgendeiner Reihenfolge — nicht sortiert. Keines von beiden sollte zum Debuggen verwendet werden, ob die Priorität stimmt — mit poll leeren, um die echte Reihenfolge zu sehen.
Der Bulk-Konstruktor hat in einem Schritt einen korrekt geordneten Heap erzeugt — das ist der lineare Heapify-Pfad.
Der Mutationsblock am Ende ist die Fußangel in konzentrierter Form. Wir haben die Priorität des Arrays nach dem Einfügen mutiert, der Heap hatte keine Möglichkeit, neu zu balancieren, und jetzt lügt peek. Der Fix besteht entweder darin, einen unveränderlichen Wrapper zu verwenden, oder nach der Änderung remove und offer aufzurufen.

Was kommt als Nächstes

Das nächste Kapitel behandelt die Implementierung, auf die man zurückgreift, wenn man eine FIFO-Warteschlange oder einen Stack oder ein Deque möchte — und diejenige, zu der das JDK-Javadoc als Standard für alle drei rät: ArrayDeque. Es ist die Klasse, die hinter den Kulissen den Großteil der Arbeit im Beispielcode der vorherigen zwei Kapitel erledigt.

Übungen

Übung

Du gibst eine `PriorityQueue<Integer>` aus, nachdem du 40, 10, 30, 20 eingefügt hast. Die Ausgabe ist `[10, 20, 30, 40]` und du schließt daraus, dass die Warteschlange 'sortiert ist'. Ein Kollege sagt: 'Verlasse dich nicht darauf.' Warum hat er recht?

Die `PriorityQueue`-Iteration durchläuft das zugrundeliegende Heap-Array in Speicherreihenfolge — nicht in Prioritätsreihenfolge; nur `poll()` gibt garantiert Elemente in aufsteigender Reihenfolge zurück`PriorityQueue` ist FIFO; die scheinbare Sortierung ist nur ein Zufall der EinfügereihenfolgeDas Javadoc besagt, dass die Iterationsreihenfolge nur undefiniert ist, wenn die Warteschlange leer ist`toString` verwendet einen separaten `Comparator`, der immer aufsteigend sortiert, aber `iterator()` nicht — sie werden sich unterscheiden