Een PriorityQueue wordt gebruikt wanneer de objecten moeten worden verwerkt op basis van de prioriteit. Het is bekend dat A Wachtrij volgt het First-In-First-Out-algoritme, maar soms moeten de elementen van de wachtrij worden verwerkt volgens de prioriteit, en dan komt de PriorityQueue in het spel.
De PriorityQueue is gebaseerd op de prioriteitsheap. De elementen van de prioriteitswachtrij worden geordend volgens de natuurlijke volgorde, of door een vergelijker die wordt geleverd tijdens het bouwen van de wachtrij, afhankelijk van welke constructor wordt gebruikt.
In de onderstaande prioriteitswachtrij heeft een element met een maximale ASCII-waarde de hoogste prioriteit.
Verklaring:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
De klas implementeert Serialiseerbaar , Itereerbaar , Verzameling , Wachtrij interfaces.
Een paar belangrijke punten over Prioriteitswachtrij zijn als volgt:
- PriorityQueue staat nul niet toe.
- We kunnen geen PriorityQueue van objecten maken die niet vergelijkbaar zijn
- PriorityQueue zijn ongebonden wachtrijen.
- De kop van deze wachtrij is het minste element met betrekking tot de opgegeven volgorde. Als meerdere elementen gelijk zijn voor de minste waarde, is de kop een van die elementen; de banden worden willekeurig verbroken.
- Omdat PriorityQueue niet thread-safe is, biedt Java de PriorityBlockingQueue-klasse die de BlockingQueue-interface implementeert voor gebruik in een Java-multithreading-omgeving.
- De bewerkingen voor het ophalen van wachtrijen pollen, verwijderen, bekijken en krijgen toegang tot het element aan het begin van de wachtrij.
- Het biedt O(log(n)) tijd voor optel- en poll-methoden.
- Het erft methoden van SamenvattingWachtrij , SamenvattingCollectie , Verzameling, En Voorwerp klas.
Constructeurs:
1. Prioriteitswachtrij(): Creëert een PriorityQueue met de standaard initiële capaciteit (11) die de elementen ordent volgens hun natuurlijke volgorde.
PriorityQueue pq = nieuwe PriorityQueue();
2. Prioriteitswachtrij (verzameling c): Creëert een PriorityQueue die de elementen in de opgegeven verzameling bevat.
PriorityQueue pq = nieuwe PriorityQueue (verzameling c);
3. Prioriteitswachtrij (int initiële capaciteit) : Creëert een PriorityQueue met de opgegeven initiële capaciteit die de elementen ordent volgens hun natuurlijke volgorde.
PriorityQueue pq = nieuwe PriorityQueue (int initialCapacity);
4. PriorityQueue (int initiële capaciteit, comparator-comparator): Creëert een PriorityQueue met de opgegeven initiële capaciteit die de elementen ordent volgens de opgegeven comparator.
PriorityQueue pq = nieuwe PriorityQueue (int initialCapacity, Comparator-comparator);
5. Prioriteitswachtrij(Prioriteitswachtrij c) : Creëert een PriorityQueue die de elementen in de opgegeven prioriteitswachtrij bevat.
PriorityQueue pq = nieuwe PriorityQueue(PriorityQueue c);
6. Prioriteitswachtrij (gesorteerde set c) : Creëert een PriorityQueue die de elementen in de opgegeven gesorteerde set bevat.
PriorityQueue pq = nieuwe PriorityQueue (SortedSet c);
7. PriorityQueue (vergelijkingsvergelijker): Creëert een PriorityQueue met de standaard initiële capaciteit en waarvan de elementen zijn geordend volgens de opgegeven comparator.
PriorityQueue pq = nieuwe PriorityQueue (vergelijker c);
Voorbeeld:
In het onderstaande voorbeeld worden de volgende basisbewerkingen van de prioriteitswachtrij uitgelegd.
voor lus in bash
- boolean add(E element): Deze methode voegt het gespecificeerde element in deze prioriteitswachtrij in.
- public peek(): Deze methode haalt de kop van deze wachtrij op, maar verwijdert deze niet, of retourneert null als deze wachtrij leeg is.
- public poll(): Deze methode haalt de kop van deze wachtrij op en verwijdert deze, of retourneert null als deze wachtrij leeg is.
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());> >}> }> |
>
>Uitvoer
10 10 15>
Bewerkingen op PriorityQueue
Laten we eens kijken hoe we enkele veelgebruikte bewerkingen op de Priority Queue-klasse kunnen uitvoeren.
1. Elementen toevoegen: Om een element aan een prioriteitswachtrij toe te voegen, kunnen we de methode add() gebruiken. De invoegopdracht wordt niet bewaard in de PriorityQueue. De elementen worden opgeslagen op basis van de prioriteitsvolgorde, die standaard oplopend is.
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);> >}> }> |
>
>Uitvoer
[0, 1, 1, 1, 2, 1]>
We krijgen geen gesorteerde elementen door PriorityQueue af te drukken.
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);> >}> }> |
>
>Uitvoer
[For, Geeks, Geeks]>
2. Elementen verwijderen: Om een element uit een prioriteitswachtrij te verwijderen, kunnen we de methode remove() gebruiken. Als er meerdere van dergelijke objecten zijn, wordt het eerste exemplaar van het object verwijderd. Daarnaast wordt de methode poll() ook gebruikt om de head te verwijderen en terug te sturen.
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);> >}> }> |
>
>Uitvoer
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Toegang tot de elementen: Omdat de wachtrij het First In First Out-principe volgt, hebben we alleen toegang tot het hoofd van de wachtrij. Om toegang te krijgen tot elementen uit een prioriteitswachtrij kunnen we de peek() -methode gebruiken.
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);> >}> }> |
>
>Uitvoer
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. De PriorityQueue herhalen: Er zijn meerdere manieren om de PriorityQueue te doorlopen. De bekendste manier is het converteren van de wachtrij naar de array en het doorlopen ervan met behulp van de for-lus. De wachtrij heeft echter ook een ingebouwde iterator die kan worden gebruikt om door de wachtrij te itereren.
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() +>' '>);> >}> >}> }> |
>
>Uitvoer
For Geeks Geeks>
Voorbeeld:
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());> >}> }> |
>
>Uitvoer
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>
Realtime voorbeelden:
Prioriteitswachtrij is een gegevensstructuur waarin elementen op prioriteit zijn geordend, waarbij de elementen met de hoogste prioriteit vooraan in de wachtrij verschijnen. Hier zijn enkele praktijkvoorbeelden van waar prioriteitswachtrijen kunnen worden gebruikt:
- Taakplanning: In besturingssystemen worden prioriteitswachtrijen gebruikt om taken te plannen op basis van hun prioriteitsniveaus. Een taak met een hoge prioriteit, zoals een kritieke systeemupdate, kan bijvoorbeeld worden gepland vóór een taak met een lagere prioriteit, zoals een back-upproces op de achtergrond. Spoedeisende hulp: Op de spoedeisende hulp van een ziekenhuis worden patiënten getriageerd op basis van de ernst van hun toestand, waarbij degenen in kritieke toestand eerst worden behandeld. Er kan een prioriteitswachtrij worden gebruikt om de volgorde te beheren waarin patiënten door artsen en verpleegkundigen worden gezien. Netwerkroutering: In computernetwerken worden prioriteitswachtrijen gebruikt om de stroom datapakketten te beheren. Pakketten met hoge prioriteit, zoals spraak- en videogegevens, kunnen voorrang krijgen boven gegevens met een lagere prioriteit, zoals e-mail en bestandsoverdracht. Transport: In verkeersmanagementsystemen kunnen prioriteitswachtrijen worden gebruikt om de verkeersstroom te beheren. Hulpvoertuigen zoals ambulances kunnen bijvoorbeeld voorrang krijgen op andere voertuigen om ervoor te zorgen dat ze hun bestemming snel kunnen bereiken. Taakplanning: In taakplanningssystemen kunnen prioriteitswachtrijen worden gebruikt om de volgorde te beheren waarin taken worden uitgevoerd. Taken met een hoge prioriteit, zoals kritieke systeemupdates, kunnen vóór taken met een lagere prioriteit, zoals gegevensback-ups, worden gepland. Online marktplaatsen: Op online marktplaatsen kunnen prioriteitswachtrijen worden gebruikt om de levering van producten aan klanten te beheren. Bestellingen met een hoge prioriteit, zoals expresverzending, kunnen voorrang krijgen op bestellingen met standaardverzending.
Over het geheel genomen zijn prioriteitswachtrijen een nuttige gegevensstructuur voor het beheren van taken en bronnen op basis van hun prioriteitsniveaus in verschillende praktijkscenario's.
Methoden in PriorityQueue-klasse
| METHODE | BESCHRIJVING |
|---|---|
| toevoegen(En en) | Voegt het opgegeven element in deze prioriteitswachtrij in. |
| duidelijk() | Verwijdert alle elementen uit deze prioriteitswachtrij. |
| comparator() | Retourneert de comparator die wordt gebruikt om de elementen in deze wachtrij te ordenen, of null als deze wachtrij is gesorteerd volgens de natuurlijke volgorde van de elementen. |
| bevat?(Object o) | Retourneert waar als deze wachtrij het opgegeven element bevat. |
| voorElk?(Consumentenactie) | Voert de gegeven actie uit voor elk element van de iterabele totdat alle elementen zijn verwerkt of de actie een uitzondering genereert. |
| iterator() | Retourneert een iterator over de elementen in deze wachtrij. |
| aanbod?(E e) | Voegt het opgegeven element in deze prioriteitswachtrij in. |
| verwijderen?(Object o) | Verwijdert één exemplaar van het opgegeven element uit deze wachtrij, als dit aanwezig is. |
| alles verwijderen? (Verzameling c) | Verwijdert alle elementen van deze verzameling die ook in de opgegeven verzameling voorkomen (optionele bewerking). |
| removeIf?(Predikaatfilter) | Verwijdert alle elementen van deze verzameling die aan het gegeven predikaat voldoen. |
| alles behouden? (Verzameling c) | Bewaart alleen de elementen in deze verzameling die zich in de opgegeven verzameling bevinden (optionele bewerking). |
| splitter() | Creëert een laatbindende en faalsnelle spliterator over de elementen in deze wachtrij. |
| toArray() | Retourneert een array die alle elementen in deze wachtrij bevat. |
| toArray?(T[] a) | Geeft een array terug die alle elementen in deze wachtrij bevat; het runtimetype van de geretourneerde array is dat van de opgegeven array. |
Methoden Gedeclareerd in klasse java.util.AbstractQueue
| METHODE | BESCHRIJVING |
|---|---|
| addAll(verzameling c) | Voegt alle elementen in de opgegeven verzameling toe aan deze wachtrij. |
| element() | Haalt de kop van deze wachtrij op, maar verwijdert deze niet. |
| verwijderen() | Haalt de kop van deze wachtrij op en verwijdert deze. |
Methoden Gedeclareerd in klasse java.util.AbstractCollection
| METHODE | BESCHRIJVING |
|---|---|
| bevatAlles(Verzameling c) | Retourneert waar als deze verzameling alle elementen in de opgegeven verzameling bevat. |
| is leeg() | Retourneert true als deze verzameling geen elementen bevat. |
| toString() | Retourneert een tekenreeksrepresentatie van deze verzameling. |
Methoden Gedeclareerd in interface java.util.Collection
| METHODE | BESCHRIJVING |
|---|---|
| bevatAlles(Verzameling c) | Retourneert waar als deze verzameling alle elementen in de opgegeven verzameling bevat. |
| is gelijk aan(Object o) | Vergelijkt het opgegeven object met deze verzameling op gelijkheid. |
| hashCode() | Retourneert de hashcodewaarde voor deze verzameling. |
| is leeg() | Retourneert true als deze verzameling geen elementen bevat. |
| parallelStream() | Retourneert een mogelijk parallelle stream met deze verzameling als bron. |
| maat() | Retourneert het aantal elementen in deze verzameling. |
| stroom() | Retourneert een sequentiële stream met deze verzameling als bron. |
| toArray(IntFunction-generator) | Retourneert een array die alle elementen in deze verzameling bevat, waarbij de meegeleverde generatorfunctie wordt gebruikt om de geretourneerde array toe te wijzen. |
Methoden Gedeclareerd in interface java.util.Queue
| METHODE | BESCHRIJVING |
|---|---|
| kijkje() | Haalt de kop van deze wachtrij op, maar verwijdert deze niet, of retourneert null als deze wachtrij leeg is. |
| opiniepeiling() | Haalt de kop van deze wachtrij op en verwijdert deze, of retourneert null als deze wachtrij leeg is. |
Toepassingen :
- Implementatie van de algoritmen van Dijkstra en Prim.
- Maximaliseer de arraysom na K-ontkenningen
gerelateerde artikelen :
cp-opdracht in Linux
- Java.util.PriorityQueue-klasse in Java
- Implementeer PriorityQueue via Comparator in Java