Java PriorityQueue

In diesem Tutorial lernen wir anhand von Beispielen die PriorityQueue-Klasse des Java-Sammlungsframeworks kennen.

Die PriorityQueueKlasse bietet die Funktionalität der Heap-Datenstruktur.

Es implementiert die Warteschlangenschnittstelle.

Im Gegensatz zu normalen Warteschlangen werden Prioritätswarteschlangenelemente in sortierter Reihenfolge abgerufen.

Angenommen, wir möchten Elemente in aufsteigender Reihenfolge abrufen. In diesem Fall ist der Kopf der Prioritätswarteschlange das kleinste Element. Sobald dieses Element abgerufen wurde, ist das nächstkleinere Element der Kopf der Warteschlange.

Es ist wichtig zu beachten, dass die Elemente einer Prioritätswarteschlange möglicherweise nicht sortiert sind. Elemente werden jedoch immer in sortierter Reihenfolge abgerufen.

PriorityQueue erstellen

Um eine Prioritätswarteschlange zu erstellen, müssen wir das java.util.PriorityQueuePaket importieren . Sobald wir das Paket importiert haben, können wir wie folgt eine Prioritätswarteschlange in Java erstellen.

 PriorityQueue numbers = new PriorityQueue();

Hier haben wir eine Prioritätswarteschlange ohne Argumente erstellt. In diesem Fall ist der Kopf der Prioritätswarteschlange das kleinste Element der Warteschlange. Und Elemente werden in aufsteigender Reihenfolge aus der Warteschlange entfernt.

Wir können jedoch die Reihenfolge der Elemente mithilfe der ComparatorBenutzeroberfläche anpassen . Wir werden später in diesem Tutorial mehr darüber erfahren.

Methoden von PriorityQueue

Die PriorityQueueKlasse bietet die Implementierung aller in der QueueSchnittstelle vorhandenen Methoden .

Fügen Sie Elemente in PriorityQueue ein

add()- Fügt das angegebene Element in die Warteschlange ein. Wenn die Warteschlange voll ist, wird eine Ausnahme ausgelöst.
offer()- Fügt das angegebene Element in die Warteschlange ein. Wenn die Warteschlange voll ist, wird sie zurückgegeben false.

Beispielsweise,

 import java.util.PriorityQueue; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); // Using the add() method numbers.add(4); numbers.add(2); System.out.println("PriorityQueue: " + numbers); // Using the offer() method numbers.offer(1); System.out.println("Updated PriorityQueue: " + numbers); ) )

Ausgabe

 PriorityQueue: (2, 4) Aktualisierte PriorityQueue: (1, 4, 2)

Hier haben wir eine Prioritätswarteschlange mit dem Namen "Nummern" erstellt. Wir haben 4 und 2 in die Warteschlange eingefügt.

Obwohl 4 vor 2 eingefügt wird, ist der Kopf der Warteschlange 2. Dies liegt daran, dass der Kopf der Prioritätswarteschlange das kleinste Element der Warteschlange ist.

Wir haben dann 1 in die Warteschlange eingefügt. Die Warteschlange wird jetzt neu angeordnet, um das kleinste Element 1 im Kopf der Warteschlange zu speichern.

Greifen Sie auf PriorityQueue-Elemente zu

Um auf Elemente aus einer Prioritätswarteschlange zuzugreifen, können wir die peek()Methode verwenden. Diese Methode gibt den Kopf der Warteschlange zurück. Beispielsweise,

 import java.util.PriorityQueue; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); numbers.add(4); numbers.add(2); numbers.add(1); System.out.println("PriorityQueue: " + numbers); // Using the peek() method int number = numbers.peek(); System.out.println("Accessed Element: " + number); ) )

Ausgabe

 PriorityQueue: (1, 4, 2) Zugriffselement: 1

Entfernen Sie PriorityQueue-Elemente

remove() - Entfernt das angegebene Element aus der Warteschlange
poll() - gibt den Kopf der Warteschlange zurück und entfernt ihn

Beispielsweise,

 import java.util.PriorityQueue; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); numbers.add(4); numbers.add(2); numbers.add(1); System.out.println("PriorityQueue: " + numbers); // Using the remove() method boolean result = numbers.remove(2); System.out.println("Is the element 2 removed? " + result); // Using the poll() method int number = numbers.poll(); System.out.println("Removed Element Using poll(): " + number); ) )

Ausgabe

PriorityQueue: (1, 4, 2) Wird das Element 2 entfernt? true Entferntes Element mit poll (): 1

Iterieren über eine PriorityQueue

Um die Elemente einer Prioritätswarteschlange zu durchlaufen, können wir die iterator()Methode verwenden. Um diese Methode verwenden zu können, müssen wir das java.util.IteratorPaket importieren . Beispielsweise,

 import java.util.PriorityQueue; import java.util.Iterator; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(); numbers.add(4); numbers.add(2); numbers.add(1); System.out.print("PriorityQueue using iterator(): "); //Using the iterator() method Iterator iterate = numbers.iterator(); while(iterate.hasNext()) ( System.out.print(iterate.next()); System.out.print(", "); ) ) )

Ausgabe

 PriorityQueue mit iterator (): 1, 4, 2,

Andere PriorityQueue-Methoden

Methoden	Beschreibungen
`contains(element)`	Durchsucht die Prioritätswarteschlange nach dem angegebenen Element. Wenn das Element gefunden wird, wird es zurückgegeben `true`, wenn nicht, wird es zurückgegeben `false`.
`size()`	Gibt die Länge der Prioritätswarteschlange zurück.
`toArray()`	Konvertiert eine Prioritätswarteschlange in ein Array und gibt es zurück.

PriorityQueue-Komparator

In allen obigen Beispielen werden Prioritätswarteschlangenelemente in der natürlichen Reihenfolge (aufsteigende Reihenfolge) abgerufen. Wir können diese Bestellung jedoch anpassen.

Dazu müssen wir eine eigene Komparatorklasse erstellen, die die ComparatorSchnittstelle implementiert . Beispielsweise,

 import java.util.PriorityQueue; import java.util.Comparator; class Main ( public static void main(String() args) ( // Creating a priority queue PriorityQueue numbers = new PriorityQueue(new CustomComparator()); numbers.add(4); numbers.add(2); numbers.add(1); numbers.add(3); System.out.print("PriorityQueue: " + numbers); ) ) class CustomComparator implements Comparator ( @Override public int compare(Integer number1, Integer number2) ( int value = number1.compareTo(number2); // elements are sorted in reverse order if (value> 0) ( return -1; ) else if (value < 0) ( return 1; ) else ( return 0; ) ) )

Ausgabe