Java-Prioritätswarteschlange: keine klassische Warteschlange

In diesem Artikel lernen wir eine Prioritätswarteschlange kennen, eine Java-Klasse, die das Queue-Interface implementiert. Was weiß ein Programmierer über das reguläre Queue-Interface? Zunächst einmal basiert dieses Interface auf dem FIFO-Prinzip, also „First In First Out“. Das erinnert an eine reguläre Warteschlange in ihrer üblichen Bedeutung. Du willst einen Kaffee vom McDrive? Wenn dein Auto das erste in der Nähe des Ausgabefensters ist, bekommst du deinen Kaffee vor dem Fahrer, der als nächstes dran ist.

Queue-Interface – Deklaration

public interface Queue<E> extends Collection<E>

Was ist eine Prioritätswarteschlange?

Was ist eine Prioritätswarteschlange? Zunächst einmal ist sie eine Klasse, die das Queue-Interface implementiert, wenn ein Element von hinten eingefügt und ein Element vom Kopf entfernt werden soll. Im Inneren ist sie jedoch keine gewöhnliche Warteschlange. Die Reihenfolge der Elemente in der Java-Prioritätswarteschlange hängt von der Priorität der Elemente ab. Das Element mit der höchsten Priorität wird an den Anfang der Warteschlange gestellt. Wenn du das ranghöchste Element löschst (abarbeitest), übernimmt das zweithöchste Element die Spitze und bekommt als nächstes seinen Kaffee. Wie wird die Priorität bestimmt? Laut der Dokumentation werden die Elemente der Prioritätswarteschlange nach ihrer natürlichen Reihenfolge oder nach einem Comparator geordnet, der bei der Erstellung der Warteschlange angegeben wird, je nachdem, welcher Konstruktor verwendet wird. Eine Prioritätswarteschlange basiert auf einem Min-Heap für die Priorität. Das bedeutet, dass im Falle von Zahlen in der Warteschlange das erste Element der Warteschlange die kleinste dieser Zahlen sein wird. Nachdem sie diese Definition gelesen haben, denken Einsteiger oft, dass die Warteschlange linear sortiert ist. Das heißt, wenn wir zum Beispiel eine Warteschlange verwenden, deren Elemente natürliche Zahlen sind, dann ist das erste Element die kleinste und das letzte Element die größte Zahl. Das ist aber nicht ganz richtig. Um zu verstehen, wie die Prioritätswarteschlange tatsächlich funktioniert und was sie leistet, musst du verstehen, wie der Heap funktioniert. Wir betrachten die interne Struktur der Prioritätswarteschlange etwas später anhand eines Beispiels. Zunächst wollen wir uns mit den äußeren Merkmalen befassen.

Konstruktoren und Deklaration der Klasse PriorityQueue

Die Klasse PriorityQueue bietet 6 verschiedene Möglichkeiten, eine Prioritätswarteschlange in Java zu erstellen.

• PriorityQueue() – leere Warteschlange mit der standardmäßigen Anfangskapazität (11), die ihre Elemente nach ihrer natürlichen Reihenfolge ordnet.
• PriorityQueue(Collection c) – leere Warteschlange, die die Elemente der angegebenen Collection enthält.
• PriorityQueue(int initialCapacity) – leere Warteschlange mit der angegebenen Anfangskapazität, die ihre Elemente nach ihrer natürlichen Reihenfolge ordnet.
• PriorityQueue(int initialCapacity, Comparator comparator) – leere Warteschlange mit der angegebenen Anfangskapazität, die ihre Elemente nach dem angegebenen Comparator ordnet.
• PriorityQueue(PriorityQueue c) – leere Warteschlange, die die Elemente der angegebenen Prioritätswarteschlange enthält.
• PriorityQueue(SortedSet c) – leere Warteschlange, die die Elemente der angegebenen sortierten Menge enthält.

Die Prioritätswarteschlange in Java wird auf folgende Weise deklariert:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

PriorityQueue erstellen

Erstellen wir einmal eine Prioritätswarteschlange mit Integer-Werten. Implementierung der Prioritätswarteschlange, Java-Code:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Wir haben eine Prioritätswarteschlange ohne Argumente erstellt. In diesem Fall ist der Kopf der Prioritätswarteschlange die kleinste Zahl der Warteschlange. Wenn du den Kopf entfernst, nimmt das nächstkleinere Element diesen Platz ein. So kannst du Elemente in aufsteigender Reihenfolge aus der Warteschlange entfernen. Bei Bedarf kannst du das Ordnungsprinzip über die Schnittstelle Comparator ändern.

Java PriorityQueue-Methoden

Die Java-Klasse PriorityQueue hat wichtige Methoden zum Hinzufügen, Entfernen und Überprüfen von Elementen.

Elemente in die Prioritätswarteschlange einfügen

• boolean add(object) fügt das angegebene Element in die Prioritätswarteschlange ein. Gibt im Erfolgsfall true zurück. Wenn die Warteschlange voll ist, löst die Methode eine Ausnahme aus.
• boolean offer(object) fügt das angegebene Element in diese Prioritätswarteschlange ein. Wenn die Warteschlange voll ist, gibt die Methode false zurück.

Du kannst beide Methoden zum Hinzufügen verwenden; in den meisten Fällen gibt es keine Unterschiede. Hier ist ein kurzes Beispiel für das Erstellen einer Prioritätswarteschlange und das Hinzufügen von Elementen.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

Die Ausgabe ist:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

Die Reihenfolge der Elemente scheint etwas seltsam. Wir werden uns das später ansehen.

Abrufen und Entfernen von Elementen aus der Prioritätswarteschlange

• boolean remove(object) entfernt eine einzelne Instanz des angegebenen Elements aus dieser Warteschlange, sofern sie vorhanden ist.
• Object poll() ruft den Kopf dieser Warteschlange ab und entfernt ihn. Gibt null zurück, wenn die Warteschlange leer ist.
• void clear() entfernt alle Elemente aus der Prioritätswarteschlange.
• Object element() ruft den Kopf dieser Warteschlange ab, ohne ihn zu entfernen. Löst eine NoSuchElementException aus, wenn die Warteschlange leer ist.
• Object peek() ruft den Kopf der Warteschlange ab, ohne ihn zu entfernen. Gibt null zurück, wenn die Warteschlange leer ist.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Die Ausgabe:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Wie du siehst, führt der Versuch, den Kopf der leeren Warteschlange mit der Methode element() auszugeben, zu einer NoSuchElementexception.

PriorityQueue – Comparator

• Comparator comparator() gibt den Comparator zurück, mit dem die Elemente in der Warteschlange geordnet wurden. Gibt null zurück, wenn die Warteschlange nach der natürlichen Reihenfolge ihrer Elemente sortiert ist.

Java-Prioritätswarteschlange, Beispiel mit Comparator

In den obigen Codebeispielen haben wir die natürliche (aufsteigende) Reihenfolge verwendet, aber manchmal müssen wir diese auch ändern. Hier findest du ein Beispiel für eine Java-Prioritätswarteschlange, in der wir unsere eigene interne Comparator-Klasse erstellen, welche wiederum das Comparator-Interface implementiert. Unser Comparator sortiert die Elemente vom größten Wert zum kleinsten Wert.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Die Ausgabe:

the head of Queue = 5
5
4
3
2
1

Der Kopf der Warteschlange ist jetzt nicht mehr das kleinste, sondern das größte Element, und die Reihenfolge wurde umgekehrt.

Iterieren über PriorityQueue mit Iterator

ProrityQueue ist ein Teil des Collection-Frameworks und implementiert das Interface Iterable<>. Um über die Elemente einer Prioritätswarteschlange zu iterieren, kannst du die Methode iterator() verwenden. Hier ist ein Beispiel:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Die Ausgabe:

1 2 4 5 3 

Weitere PriorityQueue-Methoden

• boolean contains(Object o) gibt true zurück, wenn die Warteschlange das Element o enthält.
• int size() gibt die Anzahl der Elemente in dieser Warteschlange zurück.
• Object[] toArray() gibt ein Array zurück, das alle Elemente in dieser Warteschlange enthält.

Hier ist ein Beispiel:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Die Ausgabe:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8 – Definition

Wenn du die Dokumentation von PriorityQueue in Java 8 öffnest, findest du dort die nächste Definition: Eine unbegrenzte Prioritätswarteschlange, die auf einem Priority-Heap basiert. Die Elemente der Prioritätswarteschlange werden nach ihrer natürlichen Reihenfolge oder nach einem Comparator geordnet, der bei der Erstellung der Warteschlange angegeben wird, je nachdem, welcher Konstruktor verwendet wird. Eine Prioritätswarteschlange lässt keine Nullelemente zu. Eine Prioritätswarteschlange, die auf einer natürlichen Reihenfolge beruht, erlaubt außerdem nicht das Einfügen von nicht vergleichbaren Objekten (dies kann zu einer ClassCastException führen). Heap ist hier ein sehr wichtiges Wort. Es erklärt die Eigenschaften der Reihenfolge der Elemente in der Prioritätswarteschlange.

Das Prinzip der PriorityQueue: Binärer Heap

Beginnen wir mit einem Beispiel. Lass uns zwei Objekte erstellen, die das Queue-Interface implementieren. Eines davon ist LinkedList, das zweite PriorityQueue. Beide enthalten 5 Integer-Elemente (1, 2, 3, 4 und 5) und wir beginnen, die Elemente in unsere Warteschlangen einzustellen, vom größten zum kleinsten. Wir beginnen also mit 5, dann folgen 4, 3, 2 und schließlich 1. Dann geben wir beide Listen aus und überprüfen die Reihenfolge der Elemente.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Das Ergebnis dieses Codes sieht so aus:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Okay, die Reihenfolge der LinkedList ist vorhersehbar und verständlich. Sie wird nach dem FIFO-Prinzip geordnet. Wir haben mit 5 angefangen, also ist dieses Element das allererste in der Zeile, dann kommt 4 und so weiter. Was können wir über die Reihenfolge in den Warteschlangen sagen? In der Dokumentation steht, dass die Elemente der Prioritätswarteschlange nach ihrer natürlichen Reihenfolge oder nach einem Comparator geordnet werden, der bei der Erstellung der Warteschlange angegeben wird. Allerdings scheint diese Reihenfolge nicht „natürlich“ im Sinne einer linearen Sortierung zu sein. Wir würden eher [1, 2, 3, 4, 5] erwarten und nicht [1, 2, 4, 5, 3]. Um zu verstehen, warum die Reihenfolge des Abrufs so aussieht, wie sie ist, sollten wir uns daran erinnern, dass die Prioritätswarteschlange auf einem Heap basiert. Was ist der Heap? Es handelt sich um eine Datenstruktur, die auf einem Binärbaum basiert. Die wichtigste Eigenschaft des Heaps: Die Priorität jedes übergeordneten Elements (Parent) ist größer als die Prioritäten seiner untergeordneten Elemente (Children). Ich möchte dich daran erinnern, dass ein Baum als vollständig binär bezeichnet wird, wenn jedes Parent-Element nicht mehr als zwei Child-Elemente hat und das Auffüllen der Ebenen von oben nach unten (ausgehend von derselben Ebene – von links nach rechts) erfolgt. Der binäre Heap reorganisiert sich jedes Mal, wenn Elemente hinzugefügt oder entfernt werden. Bei einem Min-Heap wird das kleinste Element an die Wurzel gesetzt, unabhängig von der Reihenfolge des Einfügens. Die Prioritätswarteschlange basiert auf diesem Min-Heap. Das bedeutet, dass im Falle von Zahlen in der Warteschlange das erste Element der Warteschlange die kleinste dieser Zahlen sein wird. Wenn du die Wurzel löschst, wird das nächstkleinere Element zu einer Wurzel.

Wenden wir uns unserem Beispiel zu.

Schritt 1. Wir stellen „5“ in die Prioritätswarteschlange ein. Sie wird zu einer Wurzel.
Schritt 2. Wir stellen „4“ in die Prioritätswarteschlange ein. 4 < 5, also sollte das neue Element höher sein als das alte. Die 4 wird zu einer Wurzel, die 5 ist ihr linkes Child-Element. Die Datenstruktur in Java ist jetzt [4, 5]
Schritt 3. Wir fügen „3“ hinzu. Sie wird vorübergehend zum rechten Child-Element einer Wurzel (4). Aber 3 < 4, also sollten wir sie nach oben befördern. Wir vertauschen 3 und 4. Jetzt haben wir die Struktur [3, 5, 4]
Schritt 4. Wir fügen „2“ hinzu. Sie wird ein linkes Child-Element von 5. 2 < 5, also vertauschen wir sie. 2 wird ein linkes Child-Element von 3. 2 < 3, also wieder vertauschen. Jetzt haben wir die Struktur [2, 3, 4, 5]
Schritt 5. Wir fügen „1“ hinzu. Sie wird vom rechten Child-Element der 3 zum linken Child-Element der 2 und geht dann zur Wurzel. Wir erhalten schließlich die Datenstruktur: [1, 2, 4, 5, 3] Die Methode zum Entfernen beginnt mit einer Wurzel und führt zu den umgekehrten Vorgängen. Zuerst haben wir also 1 als Wurzel, dann 2, 3, 4 und zuletzt 5. Deshalb erhalten wir durch das Entfernen mit poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

„sortiert“ im linearen Sinn die Ausgabe:

1
2
3
4
5

Die Prioritätswarteschlange kann also für verschiedene Vorgänge sinnvoll sein. Es dauert O(log N) Zeit, jedes Element einzufügen und zu löschen, und du kannst das kleinste Element in O(1) erhalten. Hier ist das vollständige Beispiel:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Es ist wichtig zu verstehen, dass Prioritätswarteschlangen auf binären Heaps basieren, d. h. sie speichern die Elemente nicht in linear sortierter Reihenfolge. Jeder Weg von der Wurzel zum Blatt ist geordnet, aber verschiedene Wege von der Wurzel sind es nicht. Das bedeutet, dass du das kleinste Element der Warteschlange sehr schnell abrufen kannst.

Was du über die Prioritätswarteschlange wissen solltest. Kurze Liste

• Die Prioritätswarteschlange erlaubt keine NULL-Objekte.
• Du kannst nur vergleichbare Objekte in die PriorityQueue aufnehmen.
• Die Prioritätswarteschlange wird als Min-Heap, eine Art binärer Baum, aufgebaut. Das kleinste Element ist eine Wurzel. Die Objekte der Prioritätswarteschlange sind standardmäßig in natürlicher Reihenfolge angeordnet.
• Du kannst Comparator verwenden, wenn du eine individuelle Reihenfolge benötigst.
• PriorityQueue ist nicht thread-sicher, daher solltest du in einer nebenläufigen Umgebung besser PriorityBlockingQueue verwenden.
• PriorityQueue bietet O(log(n)) Zeit für die Methoden add und poll und O(1) für den Abruf der kleinsten Elemente.