PriorityQueue in Java (mit Beispiel)

In diesem Teil der Tutorialserie stelle ich dir eine Queue vor, die streng genommen gar keine Queue ist: die PriorityQueue.

Wir befinden uns hier in der Klassenhierarchie:

Was ist eine Priority Queue?

Eine Priority Queue (deutsch: Vorrangwarteschlange) ist keine Queue im klassischen Sinne. Denn die Elemente werden nicht in FIFO-Reihenfolge entnommen, sondern entsprechend ihrer Priorität. Es wird immer das Element mit der höchsten Priorität zuerst entnommen – unabhängig davon, wann es in die Queue eingefügt wurde.

Das folgende Beispiel zeigt eine Priority Queue mit Elementen der Priorität 10 (höchste Priorität), 20, usw. bis 80 (niedrigste Priorität). Ein weiteres Element mit Priorität 45 wird in die Queue eingefügt. Die Queue sorgt dann automatisch dafür, dass dieses Element nach dem Element mit der Priorität 40 und vor dem Element mit der Priorität 50 entnommen wird.

Einfügen eines Elements in eine PriorityQueue

Mit welcher Datenstruktur wird eine Priority Queue implementiert?

Priority Queues werden in der Regel mit einem Heap implementiert.

Im letzten Teil dieser Tutorialserie werde ich dir zeigen, wie du selbst eine Priority Queue mit einem Heap implementieren kannst.

Eigenschaften der Java-PriorityQueue

Bei der Klasse java.util.PriorityQueue ergibt sich die Dequeue-Reihenfolge entweder aus der natürlichen Ordnung¹ der Elemente oder entsprechend eines dem Constructor übergebenen Comparators¹. Die zugrundeliegende Datenstruktur ist ein Min-Heap, d. h. am Kopf der Queue befindet sich immer das kleinste Element.

Die Sortierung ist dabei nicht stabil, d. h. zwei Elemente, die entsprechend der Sortierreihenfolge an gleicher Position stehen, werden nicht zwangsläufig in derselben Reihenfolge entnommen, wie sie in die Queue eingefügt wurden.

PriorityQueue ist weder threadsicher noch blockierend. Als threadsicheres, blockierendes Pendant gibt es die PriorityBlockingQueue.

Die Queue-Eigenschaften sind:

Unterliegende Datenstruktur	Thread-safe?	Blocking/ Non-blocking	Bounded/ Unbounded	Iterator Type
Min-Heap (gespeichert in einem Array)	Nein	Non-blocking	Unbounded	Fail-fast²

Die PriorityQueue verstößt übrigens nicht gegen das Liskovsche Substitutionsprinzip (Liskov substitution principle, LSP). Denn die Dokumentation des Queue-Interfaces besagt: "Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner."

¹ Alles über die "natürliche Ordnung" von Objekten und die Sortierung per Comparator liest du im Artikel "Vergleichen von Objekten in Java".

² Fail-fast: Der Iterator wirft eine ConcurrentModificationException, wenn während der Iteration Elemente in die Queue eingefügt oder aus dieser entnommen werden.

Einsatzempfehlung

Die PriorityQueue kann genau dann eingesetzt werden, wenn eine nicht threadsichere Queue mit oben beschriebener Dequeue-Reihenfolge benötigt wird.

Allerdings ist zu beachten, dass die PriorityQueue im JDK nur an sehr wenigen Stellen eingesetzt wird und somit eine gewisse Wahrscheinlichkeit für das Vorhandensein von Bugs existiert (was wenig genutzt wird, wird auch wenig getestet).

PriorityQueue Beispiel

Das folgende Beispiel zeigt, wie in Java eine Priority Queue erstellt wird und wie mehrere Zufallszahlen in die Queue geschrieben und dann wieder entnommen werden (→ Code auf GitHub).

Wir geben keinen Comparator an, d. h. die Integer-Elemente werden entsprechend ihrer natürlichen Ordnung sortiert.

public class PriorityQueueExample {
  public static void main(String[] args) {
    Queue<Integer> queue = new PriorityQueue<>();

    // Enqueue random numbers
    for (int i = 0; i < 8; i++) {
      int element = ThreadLocalRandom.current().nextInt(100);
      queue.offer(element);
      System.out.printf("queue.offer(%2d)    -->  queue = %s%n", element, queue);
    }

    // Dequeue all elements
    while (!queue.isEmpty()) {
      Integer element = queue.poll();
      System.out.printf("queue.poll() = %2d  -->  queue = %s%n", element, queue);
    }
  }
}Code-Sprache: Java (java)

Es folgt eine beispielhafte Ausgabe des Programms.

queue.offer(80)    -->  queue = [80]
queue.offer(14)    -->  queue = [14, 80]
queue.offer(10)    -->  queue = [10, 80, 14]
queue.offer(50)    -->  queue = [10, 50, 14, 80]
queue.offer( 9)    -->  queue = [9, 10, 14, 80, 50]
queue.offer(58)    -->  queue = [9, 10, 14, 80, 50, 58]
queue.offer(41)    -->  queue = [9, 10, 14, 80, 50, 58, 41]
queue.offer( 1)    -->  queue = [1, 9, 14, 10, 50, 58, 41, 80]
queue.poll() =  1  -->  queue = [9, 10, 14, 80, 50, 58, 41]
queue.poll() =  9  -->  queue = [10, 41, 14, 80, 50, 58]
queue.poll() = 10  -->  queue = [14, 41, 58, 80, 50]
queue.poll() = 14  -->  queue = [41, 50, 58, 80]
queue.poll() = 41  -->  queue = [50, 80, 58]
queue.poll() = 50  -->  queue = [58, 80]
queue.poll() = 58  -->  queue = [80]
queue.poll() = 80  -->  queue = []Code-Sprache: Klartext (plaintext)

Es ist gut zu sehen:

wie acht Elemente in die Priority Queue eingefügt werden,
wie die Elemente in der Priority Queue in vermeintlich zufälliger Reihenfolge dargestellt werden (tatsächlich handelt es sich um die Array-Repräsentation des Min-Heaps),
dass das kleinste Element immer am Kopf der Queue (links) ist,
wie die Elemente in aufsteigender Reihenfolge entnommen werden.

PriorityQueue mit einem Comparator

Im vorherigen Beispiel haben wir eine PriorityQueue über den Default-Konstruktor erstellt. Dies führt dazu, dass die Elemente entsprechend ihrer natürlichen Ordnung sortiert werden.

Wir können aber auch einen benutzerdefinierten Comparator für die Priority Queue angeben. Im folgenden Beispiel erstellen wir dazu Tasks mit je einem Namen und einer Priorität. Diese Tasks sollen nach Priorität sortiert wieder entnommen werden.

Den Comparator dafür definieren wir ganz einfach als:

Comparator<Task> comparator = Comparator.comparing(Task::name);Code-Sprache: Java (java)

Falls du mit dieser Schreibweise nicht vertraut bist – sie erstellt einen Comparator, der Tasks nach Priorität sortiert. Das ist doch viel besser lesbar als der folgende, mit einem Lambda, definierte Comparator:

Comparator<Task> comparator =
    (task1, task2) -> Integer.compare(task1.priority(), task2.priority());Code-Sprache: Java (java)

Hier der vollständige Beispiel-Code (Klasse PriorityQueueWithCustomComparatorExample auf GitHub):

public class PriorityQueueWithCustomComparatorExample {
  public static void main(String[] args) {
    Comparator<Task> comparator = Comparator.comparingInt(Task::priority);
    Queue<Task> queue = new PriorityQueue<>(comparator);

    // Enqueue tasks with random priorities
    for (int i = 0; i < 5; i++) {
      String name = "Task " + (i + 1);
      int priority = ThreadLocalRandom.current().nextInt(10, 100);
      Task task = new Task(name, priority);
      queue.offer(task);
      System.out.printf("queue.offer(%s)    -->  queue = %s%n", task, queue);
    }

    // Dequeue all elements
    while (!queue.isEmpty()) {
      System.out.printf("queue.poll() = %s  -->  queue = %s%n", queue.poll(), queue);
    }
  }

  private record Task(String name, int priority) {
    @Override
    public String toString() {
      return name + " (prio " + priority + ")";
    }
  }
}Code-Sprache: Java (java)

Eine beispielshafte Ausgabe sieht wie folgt aus:

queue.offer(Task 1 (prio 93))    -->  queue = [Task 1 (prio 93)]
queue.offer(Task 2 (prio 76))    -->  queue = [Task 2 (prio 76), Task 1 (prio 93)]
queue.offer(Task 3 (prio 92))    -->  queue = [Task 2 (prio 76), Task 1 (prio 93), Task 3 (prio 92)]
queue.offer(Task 4 (prio 51))    -->  queue = [Task 4 (prio 51), Task 2 (prio 76), Task 3 (prio 92), Task 1 (prio 93)]
queue.offer(Task 5 (prio 35))    -->  queue = [Task 5 (prio 35), Task 4 (prio 51), Task 3 (prio 92), Task 1 (prio 93), Task 2 (prio 76)]
queue.poll() = Task 5 (prio 35)  -->  queue = [Task 4 (prio 51), Task 2 (prio 76), Task 3 (prio 92), Task 1 (prio 93)]
queue.poll() = Task 4 (prio 51)  -->  queue = [Task 2 (prio 76), Task 1 (prio 93), Task 3 (prio 92)]
queue.poll() = Task 2 (prio 76)  -->  queue = [Task 3 (prio 92), Task 1 (prio 93)]
queue.poll() = Task 3 (prio 92)  -->  queue = [Task 1 (prio 93)]
queue.poll() = Task 1 (prio 93)  -->  queue = []
Code-Sprache: Klartext (plaintext)

Wir können gut erkennen, wie die Tasks entsprechend ihrer Priorität (Prio 51 zuerst, Prio 93 zuletzt) entnommen werden.

Um die Tasks nach Name alphabetisch sortiert zu entnehmen, bräuchten wir lediglich den Comparator ändern in:

Comparator<Task> comparator = Comparator.comparing(Task::name);Code-Sprache: Java (java)

PriorityQueue Zeitkomplexität

Der Aufwand für die Enqueue- und Dequeue-Operationen bei der Java-PriorityQueue gleicht dem Aufwand für das Einfügen in und Entnehmen aus einem Heap.

Die Zeitkomplexität für beide Operationen lautet somit: O(n log n)

Durch die Verwendung eines Heaps befindet sich das Element mit der höchsten Priority immer automatisch am Kopf der Queue und kann mit konstantem Aufwand entnommen werden.

Die Zeitkomplexität für die Peek-Operation beträgt somit: O(1)

(Hier findest du eine Einführung in das Thema Zeitkomplexität.)

Zusammenfassung und Ausblick

Dieser Artikel hat erklärt, was eine Priority Queue im allgemeinen ist, welche Eigenschaften die Java-PriorityQueue hat, wann man sie einsetzt, wie man die Dequeue-Reihenfolge mit einem benutzerdefinierten Comparator festlegt und welche Zeitkomplexitäten die Operationen der Priority Queue aufweisen.

Im folgenden Artikel kommen wir zur ersten blockierenden Queue, der LinkedBlockingQueue.

Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.