Eine PriorityQueue wird verwendet, wenn die Objekte nach Priorität verarbeitet werden sollen. Es ist bekannt, dass a Warteschlange folgt dem First-In-First-Out-Algorithmus, aber manchmal müssen die Elemente der Warteschlange entsprechend der Priorität verarbeitet werden, dann kommt die PriorityQueue ins Spiel.
Die PriorityQueue basiert auf dem Prioritätsheap. Die Elemente der Prioritätswarteschlange werden entsprechend der natürlichen Reihenfolge oder durch einen Komparator geordnet, der zum Zeitpunkt der Warteschlangenerstellung bereitgestellt wird, je nachdem, welcher Konstruktor verwendet wird.
In der folgenden Prioritätswarteschlange hat ein Element mit einem maximalen ASCII-Wert die höchste Priorität.
Erklärung:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Die Klasse implementiert Serialisierbar , Wiederholbar , Sammlung , Warteschlange Schnittstellen.
Ein paar wichtige Punkte in der Prioritätswarteschlange sind wie folgt:
- PriorityQueue lässt keine Null zu.
- Wir können keine PriorityQueue von Objekten erstellen, die nicht vergleichbar sind
- PriorityQueue sind ungebundene Warteschlangen.
- Der Kopf dieser Warteschlange ist das kleinste Element in Bezug auf die angegebene Reihenfolge. Wenn mehrere Elemente den geringsten Wert haben, ist der Kopf eines dieser Elemente – Bindungen werden willkürlich aufgehoben.
- Da PriorityQueue nicht threadsicher ist, stellt Java die Klasse PriorityBlockingQueue bereit, die die BlockingQueue-Schnittstelle zur Verwendung in einer Java-Multithreading-Umgebung implementiert.
- Die Warteschlangenabrufvorgänge fragen, entfernen, prüfen und greifen auf das Element an der Spitze der Warteschlange zu.
- Es bietet O(log(n)) Zeit für Add- und Poll-Methoden.
- Es erbt Methoden von AbstractQueue , AbstractCollection , Sammlung, Und Objekt Klasse.
Konstrukteure:
1. PriorityQueue(): Erstellt eine PriorityQueue mit der standardmäßigen Anfangskapazität (11), die ihre Elemente entsprechend ihrer natürlichen Reihenfolge anordnet.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (Sammlung c): Erstellt eine PriorityQueue, die die Elemente in der angegebenen Sammlung enthält.
PriorityQueue pq = new PriorityQueue(Collection c);
3. PriorityQueue(int initialCapacity) : Erstellt eine PriorityQueue mit der angegebenen Anfangskapazität, die ihre Elemente entsprechend ihrer natürlichen Reihenfolge anordnet.
PriorityQueue pq = new PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, Comparator comparator): Erstellt eine PriorityQueue mit der angegebenen Anfangskapazität, die ihre Elemente gemäß dem angegebenen Komparator ordnet.
PriorityQueue pq = new PriorityQueue(int initialCapacity, Comparator comparator);
5. PriorityQueue(PriorityQueue c) : Erstellt eine PriorityQueue, die die Elemente in der angegebenen Prioritätswarteschlange enthält.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue(SortedSet c) : Erstellt eine PriorityQueue, die die Elemente im angegebenen sortierten Satz enthält.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue(Komparator Komparator): Erstellt eine PriorityQueue mit der standardmäßigen Anfangskapazität und deren Elemente gemäß dem angegebenen Komparator geordnet sind.
PriorityQueue pq = new PriorityQueue(Comparator c);
Beispiel:
Das folgende Beispiel erläutert die folgenden grundlegenden Vorgänge der Prioritätswarteschlange.
So blockieren Sie YouTube-Werbung auf Android
- boolean add(E element): Diese Methode fügt das angegebene Element in diese Prioritätswarteschlange ein.
- public peek(): Diese Methode ruft den Kopf dieser Warteschlange ab, entfernt ihn jedoch nicht, oder gibt null zurück, wenn diese Warteschlange leer ist.
- public poll(): Diese Methode ruft den Kopf dieser Warteschlange ab und entfernt sie oder gibt null zurück, wenn diese Warteschlange leer ist.
Java
// Java program to demonstrate the> // working of PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue =>new> PriorityQueue();> >// Adding items to the pQueue using add()> >pQueue.add(>10>);> >pQueue.add(>20>);> >pQueue.add(>15>);> >// Printing the top element of PriorityQueue> >System.out.println(pQueue.peek());> >// Printing the top element and removing it> >// from the PriorityQueue container> >System.out.println(pQueue.poll());> >// Printing the top element again> >System.out.println(pQueue.peek());> >}> }> |
>
>Ausgabe
10 10 15>
Operationen auf PriorityQueue
Sehen wir uns an, wie Sie einige häufig verwendete Vorgänge für die Priority Queue-Klasse ausführen.
1. Elemente hinzufügen: Um ein Element zu einer Prioritätswarteschlange hinzuzufügen, können wir die Methode add() verwenden. Die Einfügungsreihenfolge wird nicht in der PriorityQueue beibehalten. Die Elemente werden nach der standardmäßig aufsteigenden Prioritätsreihenfolge gespeichert.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>Ausgabe
[0, 1, 1, 1, 2, 1]>
Durch das Drucken von PriorityQueue erhalten wir keine sortierten Elemente.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>Ausgabe
[For, Geeks, Geeks]>
2. Elemente entfernen: Um ein Element aus einer Prioritätswarteschlange zu entfernen, können wir die Methode „remove()“ verwenden. Wenn mehrere solcher Objekte vorhanden sind, wird das erste Vorkommen des Objekts entfernt. Darüber hinaus wird die Methode poll() auch verwendet, um den Kopf zu entfernen und zurückzugeben.
Java
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'Initial PriorityQueue '> + pq);> >// using the method> >pq.remove(>'Geeks'>);> >System.out.println(>'After Remove - '> + pq);> >System.out.println(>'Poll Method - '> + pq.poll());> >System.out.println(>'Final PriorityQueue - '> + pq);> >}> }> |
>
>Ausgabe
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Zugriff auf die Elemente: Da die Warteschlange dem Prinzip „First In First Out“ folgt, können wir nur auf den Kopf der Warteschlange zugreifen. Um auf Elemente aus einer Prioritätswarteschlange zuzugreifen, können wir die Methode peek() verwenden.
Java
Generizität in Java
// Java program to access elements> // from a PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String[] args)> >{> >// Creating a priority queue> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'PriorityQueue: '> + pq);> >// Using the peek() method> >String element = pq.peek();> >System.out.println(>'Accessed Element: '> + element);> >}> }> |
>
>Ausgabe
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Iterieren der PriorityQueue: Es gibt mehrere Möglichkeiten, die PriorityQueue zu durchlaufen. Die bekannteste Methode ist die Konvertierung der Warteschlange in ein Array und das Durchlaufen mithilfe der for-Schleife. Die Warteschlange verfügt jedoch auch über einen integrierten Iterator, der zum Durchlaufen der Warteschlange verwendet werden kann.
Java
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>' '>);> >}> >}> }> |
>
>Ausgabe
For Geeks Geeks>
Beispiel:
Java
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>Ausgabe
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
Echtzeit-Beispiele:
Die Prioritätswarteschlange ist eine Datenstruktur, in der Elemente nach Priorität geordnet sind, wobei die Elemente mit der höchsten Priorität am Anfang der Warteschlange erscheinen. Hier sind einige Beispiele aus der Praxis, wo Prioritätswarteschlangen verwendet werden können:
- Aufgabenplanung: In Betriebssystemen werden Prioritätswarteschlangen verwendet, um Aufgaben basierend auf ihren Prioritätsstufen zu planen. Beispielsweise kann eine Aufgabe mit hoher Priorität wie ein kritisches Systemupdate vor einer Aufgabe mit niedrigerer Priorität wie einem Hintergrundsicherungsprozess geplant werden. Notaufnahme: In der Notaufnahme eines Krankenhauses werden Patienten anhand der Schwere ihrer Erkrankung eingeteilt, wobei diejenigen in kritischem Zustand zuerst behandelt werden. Mithilfe einer Prioritätswarteschlange kann die Reihenfolge verwaltet werden, in der Patienten von Ärzten und Pflegekräften behandelt werden. Netzwerkrouting: In Computernetzwerken werden Prioritätswarteschlangen verwendet, um den Fluss von Datenpaketen zu verwalten. Paketen mit hoher Priorität wie Sprach- und Videodaten kann Vorrang vor Daten mit niedrigerer Priorität wie E-Mail und Dateiübertragungen eingeräumt werden. Transport: In Verkehrsmanagementsystemen können Prioritätswarteschlangen zur Steuerung des Verkehrsflusses verwendet werden. Beispielsweise kann Einsatzfahrzeugen wie Krankenwagen Vorrang vor anderen Fahrzeugen eingeräumt werden, um sicherzustellen, dass sie ihr Ziel schnell erreichen. Jobplanung: In Jobplanungssystemen können Prioritätswarteschlangen verwendet werden, um die Reihenfolge zu verwalten, in der Jobs ausgeführt werden. Aufgaben mit hoher Priorität wie kritische Systemaktualisierungen können vor Aufgaben mit niedrigerer Priorität wie Datensicherungen geplant werden. Online-Marktplätze: Auf Online-Marktplätzen können Prioritätswarteschlangen verwendet werden, um die Lieferung von Produkten an Kunden zu verwalten. Bestellungen mit hoher Priorität wie Expressversand können Vorrang vor Standardversandaufträgen haben.
Insgesamt sind Prioritätswarteschlangen eine nützliche Datenstruktur für die Verwaltung von Aufgaben und Ressourcen basierend auf ihren Prioritätsstufen in verschiedenen realen Szenarien.
Methoden in der PriorityQueue-Klasse
| METHODE | BESCHREIBUNG |
|---|---|
| hinzufügen(Und und) | Fügt das angegebene Element in diese Prioritätswarteschlange ein. |
| klar() | Entfernt alle Elemente aus dieser Prioritätswarteschlange. |
| Komparator() | Gibt den Komparator zurück, der zum Ordnen der Elemente in dieser Warteschlange verwendet wird, oder null, wenn diese Warteschlange gemäß der natürlichen Reihenfolge ihrer Elemente sortiert ist. |
| enthält?(Objekt o) | Gibt true zurück, wenn diese Warteschlange das angegebene Element enthält. |
| forEach?(Verbraucheraktion) | Führt die angegebene Aktion für jedes Element des Iterable aus, bis alle Elemente verarbeitet wurden oder die Aktion eine Ausnahme auslöst. |
| Iterator() | Gibt einen Iterator über die Elemente in dieser Warteschlange zurück. |
| Angebot?(E e) | Fügt das angegebene Element in diese Prioritätswarteschlange ein. |
| entfernen?(Objekt o) | Entfernt eine einzelne Instanz des angegebenen Elements aus dieser Warteschlange, sofern vorhanden. |
| RemoveAll?(Sammlung c) | Entfernt alle Elemente dieser Sammlung, die auch in der angegebenen Sammlung enthalten sind (optionaler Vorgang). |
| removeIf?(Prädikatfilter) | Entfernt alle Elemente dieser Sammlung, die das angegebene Prädikat erfüllen. |
| keepAll?(Sammlung c) | Behält nur die Elemente in dieser Sammlung, die in der angegebenen Sammlung enthalten sind (optionaler Vorgang). |
| Splitterator() | Erstellt einen spät bindenden und ausfallsicheren Spliterator über die Elemente in dieser Warteschlange. |
| toArray() | Gibt ein Array zurück, das alle Elemente in dieser Warteschlange enthält. |
| toArray?(T[] a) | Gibt ein Array zurück, das alle Elemente in dieser Warteschlange enthält. Der Laufzeittyp des zurückgegebenen Arrays ist der des angegebenen Arrays. |
In der Klasse java.util.AbstractQueue deklarierte Methoden
| METHODE | BESCHREIBUNG |
|---|---|
| addAll(Sammlung c) | Fügt alle Elemente in der angegebenen Sammlung zu dieser Warteschlange hinzu. |
| Element() | Ruft den Kopf dieser Warteschlange ab, entfernt ihn jedoch nicht. |
| entfernen() | Ruft den Kopf dieser Warteschlange ab und entfernt ihn. |
In der Klasse java.util.AbstractCollection deklarierte Methoden
| METHODE | BESCHREIBUNG |
|---|---|
| enthältAlle(Sammlung c) | Gibt „true“ zurück, wenn diese Sammlung alle Elemente in der angegebenen Sammlung enthält. |
| ist leer() | Gibt true zurück, wenn diese Sammlung keine Elemente enthält. |
| toString() | Gibt eine Zeichenfolgendarstellung dieser Sammlung zurück. |
In der Schnittstelle java.util.Collection deklarierte Methoden
| METHODE | BESCHREIBUNG |
|---|---|
| enthältAlle(Sammlung c) | Gibt „true“ zurück, wenn diese Sammlung alle Elemente in der angegebenen Sammlung enthält. |
| equal(Objekt o) | Vergleicht das angegebene Objekt mit dieser Sammlung auf Gleichheit. |
| Hash-Code() | Gibt den Hash-Codewert für diese Sammlung zurück. |
| ist leer() | Gibt true zurück, wenn diese Sammlung keine Elemente enthält. |
| parallelStream() | Gibt einen möglicherweise parallelen Stream mit dieser Sammlung als Quelle zurück. |
| Größe() | Gibt die Anzahl der Elemente in dieser Sammlung zurück. |
| Strom() | Gibt einen sequentiellen Stream mit dieser Sammlung als Quelle zurück. |
| toArray(IntFunction-Generator) | Gibt ein Array zurück, das alle Elemente in dieser Sammlung enthält, und verwendet die bereitgestellte Generatorfunktion, um das zurückgegebene Array zuzuordnen. |
In der Schnittstelle java.util.Queue deklarierte Methoden
| METHODE | BESCHREIBUNG |
|---|---|
| spähen() | Ruft den Kopf dieser Warteschlange ab, entfernt ihn jedoch nicht, oder gibt null zurück, wenn diese Warteschlange leer ist. |
| Umfrage() | Ruft den Kopf dieser Warteschlange ab und entfernt ihn oder gibt null zurück, wenn diese Warteschlange leer ist. |
Anwendungen :
- Implementierung der Algorithmen von Dijkstra und Prim.
- Maximieren Sie die Array-Summe nach K Negationen
In Verbindung stehende Artikel :
- Java.util.PriorityQueue-Klasse in Java
- Implementieren Sie PriorityQueue über Comparator in Java