Prioritätswarteschlange Java

Tutorials
Java

Von Zeit zu Zeit müssen wir Elemente einer Warteschlange in einer bestimmten Reihenfolge verarbeiten. Eine Prioritätswarteschlange ist eine Datenstruktur, die diese Aufgabe erledigt. Die Java Prioritätswarteschlange unterscheidet sich von einer „normalen“ Warteschlange. Anstatt „First-In-First-Out“ werden die Elemente nach ihrer Priorität abgerufen.

Prioritätswarteschlange in Java

Die Klasse java.util.PriorityQueue bietet uns eine Implementierung eines solchen Datentyps, indem sie intern eine Prioritäts-Heap-Implementierung verwendet. Die Java Prioritätswarteschlange ist eine unbeschränkte Warteschlange. Sie wurde in Java 1.5 eingeführt und in der Java SE 8-Version erweitert. Die PriorityQueue wird intern durch die Datenstruktur „Prioritäts-Heap“ implementiert. Hier ist die Klassenhierarchie der PriorityQueue: Klassendiagramm von PriorityQueue:

Java PriorityQueue Konstruktoren

  1. PriorityQueue() – Erzeugt eine PriorityQueue mit der Standardanfangsgröße, d.h. 11
  2. PriorityQueue(Collection c) – Erzeugt eine PriorityQueue mit den Elementen in der angegebenen Sammlung
  3. PriorityQueue(int initialCapacity) – Erstellt eine PriorityQueue mit der angegebenen Anfangskapazität
  4. PriorityQueue(int initialCapacity, Comparator comparator) – Erstellt eine PriorityQueue mit der angegebenen Anfangskapazität und die Anordnung der Elemente erfolgt gemäß dem angegebenen Comparator
  5. PriorityQueue(PriorityQueue c) – Erstellt eine PriorityQueue, die die Elemente in der angegebenen Prioritätswarteschlange enthält
  6. PriorityQueue(SortedSet c) – Erstellt eine PriorityQueue, die die Elemente im angegebenen sortierten Satz enthält

Die Elemente der Prioritätswarteschlange sind nach ihrer natürlichen Reihenfolge geordnet, es sei denn, wir geben beim Erstellen einen Comparator an. Die Elemente sind standardmäßig in aufsteigender Reihenfolge angeordnet, daher ist der Kopf der Warteschlange das Element mit der niedrigsten Priorität. Wenn zwei Elemente gleichzeitig als Kopf geeignet sind, werden solche Bindungen willkürlich gelöst.

Java PriorityQueue Beispiel

Erstellen wir eine PriorityQueue mit verschiedenen Aufgaben:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

Dies erstellt eine PriorityQueue von Aufgaben, die nach der natürlichen Reihenfolge von String sortiert werden. Erstellen wir eine weitere PriorityQueue, die die Aufgaben in umgekehrter Reihenfolge der natürlichen Reihenfolge sortiert. Dazu müssen wir einen Comparator übergeben:

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java PriorityQueue Methoden

Werfen wir nun einen Blick auf alle verfügbaren Methoden für PriorityQueue und verwenden sie:

  1. Boolean add(E e) – Diese Methode fügt das angegebene Element in die Warteschlange ein. Wir haben bereits 5 Aufgaben in unserer Warteschlange mit dieser Methode hinzugefügt.

  2. Comparator comparator() – Diese Methode gibt den Comparator zurück, der zum Ordnen der Elemente in dieser Warteschlange verwendet wird. Sie gibt null zurück, wenn kein Comparator angegeben wurde und die Warteschlange gemäß der natürlichen Reihenfolge ihrer Elemente sortiert ist. Wenn wir also Folgendes tun:

    System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

    Wird die Ausgabe sein:

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – Gibt true zurück, wenn die Warteschlange das angegebene Element enthält. Lassen Sie uns überprüfen, ob „task3“ zur Prioritätswarteschlange tasks gehört:

    System.out.println(tasks.contains("task3"));

    Dies gibt aus:

    true

  4. boolean offer(E e) – Genau wie die add()-Methode fügt auch diese Methode ein Element zur Warteschlange hinzu. Die offer()- und add()-Methoden sind für kapazitätsbeschränkte Warteschlangen tatsächlich etwas unterschiedlich, aber im Fall von PriorityQueue sind beide gleich. Im Gegensatz zu add() wirft offer() keine Ausnahme, selbst wenn es das Element nicht in die Warteschlange einfügen kann.

  5. E peek() – Ruft das Kopfelement dieser Warteschlange ab oder gibt null zurück, wenn diese Warteschlange leer ist. Mit anderen Worten, es gibt das Element mit der höchsten Priorität zurück. Daher gibt der folgende Code aus:

    System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

    Gibt uns:

    task1
task5

  6. E poll() – Diese Methode ruft auch den Kopf der Warteschlange (Element mit höchster Priorität) ab oder gibt null zurück, wenn die Warteschlange leer ist. Aber im Gegensatz zu peek() entfernt es auch das Element. Wenn wir also poll() aufrufen:

    System.out.println(“Poll bei Aufgaben: ”+tasks.poll());
System.out.println(“Poll bei reverseTasks: ”+reverseTasks.poll());

    Und dann peek:

    System.out.println(“Peek bei Aufgaben: ”+tasks.peek());
System.out.println(“Peek bei reverseTasks: ”+reverseTasks.peek());

    Wir haben die folgende Ausgabe:

    Poll bei Aufgaben: Aufgabe1
Poll bei reverseTasks: Aufgabe5
Peek bei Aufgaben: Aufgabe2
Peek bei reverseTasks: Aufgabe4

  7. int size() – Gibt die Anzahl der Elemente in der Warteschlange zurück.

  8. boolean remove(Object o) – Entfernt das angegebene Element aus der Warteschlange, wenn es vorhanden ist. Wenn zwei gleiche Elemente vorhanden sind, wird nur eines von ihnen entfernt.

  9. Object[] toArray() – Gibt ein Array zurück, das alle Elemente in der Warteschlange enthält.

  10. T[] toArray(T[] a) – Gibt ein Array zurück, das alle Elemente in der Warteschlange enthält, und der Typ des zurückgegebenen Arrays entspricht dem des angegebenen Arrays.

  11. Iterator iterator() – Gibt einen Iterator für die Warteschlange zurück.

  12. void clear() – Entfernt alle Elemente aus der Warteschlange.

Abgesehen davon erbt die PriorityQueue auch die Methoden der Klassen Collection und Object.

Java PriorityQueue Zeitkomplexität

  1. Für die Methoden zum Ein- und Ausreihen beträgt die Zeitkomplexität O(log(n))
  2. Für die Methoden remove(Object) und contains(Object) beträgt die Zeitkomplexität linear
  3. Für die Abrufmethoden hat sie konstante Zeitkomplexität

Diese Implementierung der Prioritätswarteschlange ist nicht thread-sicher. Wenn wir also synchronisierten Zugriff benötigen, müssen wir PriorityBlockingQueue verwenden. Referenz: API-Dokumentation

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java