En PriorityQueue används när objekten ska bearbetas baserat på prioriteten. Det är känt att a Kö följer First-In-First-Out-algoritmen, men ibland krävs att köns delar bearbetas enligt prioritet, det är då PriorityQueue kommer till spel.
PriorityQueue är baserad på prioritetshögen. Elementen i prioritetskön ordnas enligt den naturliga ordningen, eller av en komparator som tillhandahålls vid kökonstruktionstid, beroende på vilken konstruktör som används.
I prioritetskön nedan kommer ett element med ett maximalt ASCII-värde att ha högsta prioritet.
Deklaration:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Klassen implementerar Serialiserbar , Iterable , Samling , Kö gränssnitt.
Några viktiga punkter på Priority Queue är följande:
- PriorityQueue tillåter inte null.
- Vi kan inte skapa en PriorityQueue av objekt som inte är jämförbara
- PriorityQueue är obundna köer.
- Huvudet för denna kö är det minsta elementet med avseende på den specificerade beställningen. Om flera element är knutna för det lägsta värdet är huvudet ett av dessa element - banden bryts godtyckligt.
- Eftersom PriorityQueue inte är trådsäker, tillhandahåller java PriorityBlockingQueue-klassen som implementerar BlockingQueue-gränssnittet för användning i en java-multithreading-miljö.
- Åtgärderna för hämtning av kö pollar, tar bort, kika och element får åtkomst till elementet längst upp i kön.
- Det ger O(log(n))-tid för add- och pollmetoder.
- Det ärver metoder från Abstrakt kö , Abstrakt samling , Samling, och Objekt klass.
Konstruktörer:
1. PriorityQueue(): Skapar en PriorityQueue med standardinledande kapacitet (11) som ordnar dess element enligt deras naturliga ordning.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (Samling c): Skapar en PriorityQueue som innehåller elementen i den angivna samlingen.
PriorityQueue pq = new PriorityQueue(Samling c);
3. PriorityQueue(int initialCapacity) : Skapar en PriorityQueue med den specificerade initiala kapaciteten som ordnar dess element enligt deras naturliga ordning.
PriorityQueue pq = new PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, Comparator comparator): Skapar en PriorityQueue med den specificerade initiala kapaciteten som ordnar dess element enligt den specificerade komparatorn.
PriorityQueue pq = new PriorityQueue(int initialCapacity, Comparator comparator);
5. PriorityQueue(PriorityQueue c) : Skapar en PriorityQueue som innehåller elementen i den angivna prioritetskön.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue(SortedSet c) : Skapar en PriorityQueue som innehåller elementen i den angivna sorterade uppsättningen.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue(Comparator comparator): Skapar en PriorityQueue med standardinledande kapacitet och vars element är ordnade enligt den specificerade komparatorn.
PriorityQueue pq = new PriorityQueue(Comparator c);
Exempel:
Exemplet nedan förklarar följande grundläggande funktioner för prioritetskön.
dfs algoritm
- boolean add(E element): Denna metod infogar det angivna elementet i denna prioritetskö.
- public peek(): Denna metod hämtar, men tar inte bort, huvudet på denna kö, eller returnerar null om den här kön är tom.
- public poll(): Denna metod hämtar och tar bort huvudet på denna kö, eller returnerar null om den här kön är tom.
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());> >}> }> |
>
>Produktion
10 10 15>
Operationer på PriorityQueue
Låt oss se hur du utför några ofta använda operationer i klassen Priority Queue.
1. Lägga till element: För att lägga till ett element i en prioritetskö kan vi använda metoden add(). Insättningsordningen behålls inte i PriorityQueue. Elementen lagras baserat på prioritetsordningen som är stigande som standard.
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);> >}> }> |
>
>Produktion
[0, 1, 1, 1, 2, 1]>
Vi kommer inte att få sorterade element genom att skriva ut PriorityQueue.
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);> >}> }> |
>
>Produktion
[For, Geeks, Geeks]>
2. Ta bort element: För att ta bort ett element från en prioritetskö kan vi använda metoden remove(). Om det finns flera sådana objekt tas den första förekomsten av objektet bort. Bortsett från det används poll()-metoden också för att ta bort huvudet och returnera det.
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);> >}> }> |
>
>Produktion
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Få åtkomst till elementen: Eftersom Queue följer First In First Out-principen, kan vi bara komma åt huvudet av kön. För att komma åt element från en prioritetskö kan vi använda metoden peek() .
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);> >}> }> |
>
>Produktion
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Iteration av Priority Queue: Det finns flera sätt att iterera genom PriorityQueue. Det mest kända sättet är att konvertera kön till arrayen och korsa med for-loopen. Men kön har också en inbyggd iterator som kan användas för att iterera genom kön.
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() +>' '>);> >}> >}> }> |
>
>
gjuta i sqlProduktion
For Geeks Geeks>
Exempel:
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());> >}> }> |
>
>Produktion
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>
Exempel i realtid:
Priority Queue är en datastruktur där element ordnas efter prioritet, där de högst prioriterade elementen visas längst fram i kön. Här är några verkliga exempel på var prioriterade köer kan användas:
- Uppgiftsschemaläggning: I operativsystem används prioritetsköer för att schemalägga uppgifter baserat på deras prioritetsnivåer. Till exempel kan en högprioriterad uppgift som en kritisk systemuppdatering schemaläggas före en lägre prioriterad uppgift som en säkerhetskopieringsprocess i bakgrunden. Akutmottagning: På akutmottagningen på sjukhuset triageras patienterna baserat på svårighetsgraden av deras tillstånd, med de i kritiskt tillstånd som behandlas först. En prioriterad kö kan användas för att hantera i vilken ordning patienter ses av läkare och sjuksköterskor. Nätverksrouting: I datornätverk används prioriterade köer för att hantera flödet av datapaket. Högprioriterade paket som röst- och videodata kan ges prioritet framför lägre prioritet som e-post och filöverföringar. Transport : I trafikledningssystem kan prioriterade köer användas för att hantera trafikflödet. Till exempel kan utryckningsfordon som ambulanser ges företräde framför andra fordon för att säkerställa att de kan nå sin destination snabbt. Jobbschemaläggning: I jobbschemaläggningssystem kan prioriterade köer användas för att hantera ordningen i vilka jobb utförs. Högprioriterade jobb som kritiska systemuppdateringar kan schemaläggas före jobb med lägre prioritet som säkerhetskopiering av data. Onlinemarknadsplatser : På onlinemarknadsplatser kan prioriterade köer användas för att hantera leveransen av produkter till kunder. Högprioriterade beställningar som expressfrakt kan ges prioritet framför standardfraktbeställningar.
Överlag är prioriterade köer en användbar datastruktur för att hantera uppgifter och resurser baserat på deras prioritetsnivåer i olika verkliga scenarier.
Metoder i klassen PriorityQueue
| METOD | BESKRIVNING |
|---|---|
| lägg till (Och och) | Infogar det angivna elementet i denna prioritetskö. |
| klar() | Tar bort alla element från denna prioritetskö. |
| komparator() | Returnerar komparatorn som används för att ordna elementen i denna kö, eller null om denna kö är sorterad enligt den naturliga ordningen av dess element. |
| innehåller?(Objekt o) | Returnerar sant om denna kö innehåller det angivna elementet. |
| för varje? (Konsumentåtgärd) | Utför den givna åtgärden för varje element i Iterable tills alla element har bearbetats eller åtgärden ger ett undantag. |
| iterator() | Returnerar en iterator över elementen i den här kön. |
| erbjuda? (E e) | Infogar det angivna elementet i denna prioritetskö. |
| ta bort? (Objekt o) | Tar bort en enstaka instans av det angivna elementet från den här kön, om den finns. |
| removeAll? (Samling c) | Tar bort alla denna samlings element som också finns i den angivna samlingen (valfri operation). |
| removeIf?(Predikatfilter) | Tar bort alla element i den här samlingen som uppfyller det givna predikatet. |
| behållaAlla?(Samling c) | Behåller endast de element i denna samling som finns i den angivna samlingen (valfri operation). |
| spliterator() | Skapar en sen bindande och misslyckad splitterator över elementen i den här kön. |
| toArray() | Returnerar en array som innehåller alla elementen i den här kön. |
| toArray?(T[] a) | Returnerar en array som innehåller alla elementen i denna kö; körtidstypen för den returnerade arrayen är den för den angivna arrayen. |
Metoder deklarerade i klassen java.util.AbstractQueue
| METOD | BESKRIVNING |
|---|---|
| addAll(Samling c) | Lägger till alla element i den angivna samlingen till den här kön. |
| element() | Hämtar, men tar inte bort, chefen för denna kö. |
| avlägsna() | Hämtar och tar bort huvudet i denna kö. |
Metoder deklarerade i klassen java.util.AbstractCollection
| METOD | BESKRIVNING |
|---|---|
| innehåller alla (samling c) | Returnerar sant om den här samlingen innehåller alla element i den angivna samlingen. |
| är tom() | Returnerar sant om den här samlingen inte innehåller några element. |
| att stränga() | Returnerar en strängrepresentation av denna samling. |
Metoder deklarerade i gränssnittet java.util.Collection
| METOD | BESKRIVNING |
|---|---|
| innehåller alla (samling c) | Returnerar sant om den här samlingen innehåller alla element i den angivna samlingen. |
| lika(Objekt o) | Jämför det angivna objektet med denna samling för jämlikhet. |
| hash-kod() | Returnerar hashkodvärdet för denna samling. |
| är tom() | Returnerar sant om den här samlingen inte innehåller några element. |
| parallellStream() | Returnerar en möjligen parallell ström med den här samlingen som källa. |
| storlek() | Returnerar antalet element i den här samlingen. |
| ström() | Returnerar en sekventiell ström med den här samlingen som källa. |
| toArray(IntFunction generator) | Returnerar en array som innehåller alla elementen i denna samling, med hjälp av den medföljande generatorfunktionen för att allokera den returnerade arrayen. |
Metoder deklarerade i gränssnittet java.util.Queue
| METOD | BESKRIVNING |
|---|---|
| titt() | Hämtar, men tar inte bort, huvudet på denna kö, eller returnerar null om denna kö är tom. |
| opinionsundersökning() | Hämtar och tar bort huvudet på denna kö, eller returnerar null om denna kö är tom. |
Ansökningar :
- Implementering av Dijkstras och Prims algoritmer.
- Maximera matrissumman efter K negationer
relaterade artiklar :
- Java.util.PriorityQueue-klass i Java
- Implementera PriorityQueue genom Comparator i Java