PriorityQueue sa používa, keď sa predpokladá, že objekty budú spracované na základe priority. Je známe, že a Fronta postupuje podľa algoritmu First-In-First-Out, ale niekedy je potrebné spracovať prvky frontu podľa priority, vtedy prichádza do hry PriorityQueue.
PriorityQueue je založený na prioritnej halde. Prvky prioritného radu sú zoradené podľa prirodzeného poradia alebo pomocou komparátora poskytnutého v čase zostavovania frontu, v závislosti od použitého konštruktora.
V nižšie uvedenom prioritnom rade bude mať prvok s maximálnou hodnotou ASCII najvyššiu prioritu.
Vyhlásenie:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Trieda implementuje Serializovateľné , Iterovateľné , Zbierka , Fronta rozhrania.
Zopár dôležité body v prioritnom rade sú nasledujúce:
- PriorityQueue nepovoľuje hodnotu null.
- Nemôžeme vytvoriť prioritný rad objektov, ktoré nie sú porovnateľné
- PriorityQueue sú neviazané fronty.
- Hlava tohto frontu je najmenší prvok vzhľadom na zadané poradie. Ak je zviazaných viacero prvkov za najmenšiu hodnotu, jedným z týchto prvkov je hlava – väzby sa lámu svojvoľne.
- Keďže PriorityQueue nie je bezpečné pre vlákna, java poskytuje triedu PriorityBlockingQueue, ktorá implementuje rozhranie BlockingQueue na použitie v prostredí Java s viacerými vláknami.
- Operácie načítania frontu zisťujú, odoberajú, nahliadajú a prvok pristupujú k prvku na začiatku frontu.
- Poskytuje čas O(log(n)) pre metódy pridávania a dotazovania.
- Dedí metódy z AbstractQueue , AbstractCollection , zbierka, a Objekt trieda.
Konštruktéri:
1. PriorityQueue(): Vytvorí PriorityQueue s predvolenou počiatočnou kapacitou (11), ktorá zoradí svoje prvky podľa ich prirodzeného usporiadania.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (Kolekcia c): Vytvorí PriorityQueue, ktorý obsahuje prvky v zadanej kolekcii.
PriorityQueue pq = new PriorityQueue(Kolekcia c);
3. PriorityQueue (int initialCapacity) : Vytvorí PriorityQueue so zadanou počiatočnou kapacitou, ktorá zoradí svoje prvky podľa ich prirodzeného usporiadania.
PriorityQueue pq = new PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, Comparator Comparator): Vytvorí PriorityQueue so zadanou počiatočnou kapacitou, ktorá zoradí svoje prvky podľa zadaného porovnávača.
PriorityQueue pq = new PriorityQueue(int initialCapacity, Comparator comparator);
5. PriorityQueue(PriorityQueue c) : Vytvorí PriorityQueue obsahujúci prvky v špecifikovanom prioritnom fronte.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue (SortedSet c) : Vytvorí PriorityQueue, ktorý obsahuje prvky v zadanej zoradenej množine.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue (porovnávač porovnania): Vytvorí PriorityQueue s predvolenou počiatočnou kapacitou a ktorého prvky sú zoradené podľa zadaného porovnávača.
PriorityQueue pq = new PriorityQueue(Comparator c);
Príklad:
Nižšie uvedený príklad vysvetľuje nasledujúce základné operácie prioritného frontu.
bash dĺžka struny
- boolean add(E element): Táto metóda vloží zadaný element do tohto prioritného frontu.
- public peek(): Táto metóda načíta, ale neodstráni hlavičku tohto frontu, alebo vráti hodnotu null, ak je tento front prázdny.
- public poll(): Táto metóda načíta a odstráni hlavičku tohto frontu alebo vráti hodnotu null, ak je tento front prázdny.
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());> >}> }> |
>
>Výkon
10 10 15>
Operácie na PriorityQueue
Pozrime sa, ako vykonať niekoľko často používaných operácií v triede Priority Queue.
1. Pridanie prvkov: Na pridanie prvku do prioritného frontu môžeme použiť metódu add(). Objednávka vloženia sa neuchová v PriorityQueue. Prvky sú uložené na základe poradia priorít, ktoré je štandardne vzostupné.
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);> >}> }> |
>
>Výkon
[0, 1, 1, 1, 2, 1]>
Tlačením PriorityQueue nezískame zoradené prvky.
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);> >}> }> |
>
>Výkon
[For, Geeks, Geeks]>
2. Odstránenie prvkov: Na odstránenie prvku z prioritného frontu môžeme použiť metódu remove(). Ak existuje viacero takýchto objektov, potom sa prvý výskyt objektu odstráni. Okrem toho sa na odstránenie hlavy a jej vrátenie používa aj metóda poll().
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);> >}> }> |
>
>Výkon
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Prístup k prvkom: Keďže Queue sa riadi princípom First In First Out, máme prístup len k vedúcemu frontu. Na prístup k prvkom z prioritného frontu môžeme použiť metódu 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);> >}> }> |
>
>Výkon
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Opakovanie fronty priorít: Existuje niekoľko spôsobov, ako iterovať cez PriorityQueue. Najznámejším spôsobom je konverzia frontu na pole a prechádzanie pomocou cyklu for. Avšak front má tiež zabudovaný iterátor, ktorý možno použiť na iteráciu cez front.
Java
java ako previesť reťazec na int
// 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() +>' '>);> >}> >}> }> |
>
>Výkon
For Geeks Geeks>
Príklad:
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());> >}> }> |
>
>Výkon
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>
Príklady v reálnom čase:
Prioritný front je dátová štruktúra, v ktorej sú prvky zoradené podľa priority, pričom prvky s najvyššou prioritou sa objavujú na začiatku frontu. Tu je niekoľko príkladov zo skutočného sveta, kde možno použiť prioritné fronty:
- Plánovanie úloh: V operačných systémoch sa prioritné fronty používajú na plánovanie úloh na základe ich úrovní priority. Napríklad úloha s vysokou prioritou, ako je kritická aktualizácia systému, môže byť naplánovaná pred úlohou s nižšou prioritou, ako je proces zálohovania na pozadí. Pohotovosť: Na pohotovosti v nemocnici sú pacienti triedení na základe závažnosti ich stavu, pričom tí v kritickom stave sú liečení ako prví. Prioritný rad možno použiť na spravovanie poradia, v ktorom sú pacienti sledovaní lekármi a sestrami. Smerovanie v sieti : V počítačových sieťach sa prioritné fronty používajú na riadenie toku dátových paketov. Pakety s vysokou prioritou, ako sú hlasové a video dáta, môžu mať prioritu pred dátami s nižšou prioritou, ako sú e-maily a prenosy súborov. Preprava : V systémoch riadenia dopravy možno na riadenie toku dopravy použiť prioritné fronty. Napríklad záchranné vozidlá, ako sú sanitky, môžu dostať prednosť pred inými vozidlami, aby sa zabezpečilo, že sa rýchlo dostanú do cieľa. Plánovanie úloh: V systémoch plánovania úloh možno prioritné fronty použiť na riadenie poradia, v ktorom sa úlohy vykonávajú. Úlohy s vysokou prioritou, ako sú kritické aktualizácie systému, môžu byť naplánované pred úlohami s nižšou prioritou, ako je napríklad zálohovanie údajov. Online trhoviská : Na online trhoviskách je možné použiť prioritné fronty na riadenie dodávky produktov zákazníkom. Objednávky s vysokou prioritou, ako je expresná doprava, môžu mať prednosť pred štandardnými zásielkovými objednávkami.
Celkovo sú prioritné fronty užitočnou dátovou štruktúrou na riadenie úloh a zdrojov na základe ich úrovní priority v rôznych scenároch reálneho sveta.
Metódy v triede PriorityQueue
| METÓDA | POPIS |
|---|---|
| pridať (a a) | Vloží zadaný prvok do tohto prioritného frontu. |
| jasný() | Odstráni všetky prvky z tohto prioritného frontu. |
| porovnávač() | Vráti komparátor použitý na zoradenie prvkov v tomto fronte alebo hodnotu null, ak je tento front zoradený podľa prirodzeného usporiadania jeho prvkov. |
| obsahuje? (Objekt o) | Vráti hodnotu true, ak tento front obsahuje zadaný prvok. |
| pre každého? (spotrebiteľská akcia) | Vykoná danú akciu pre každý prvok Iterable, kým nie sú spracované všetky prvky alebo kým akcia nevyvolá výnimku. |
| iterátor() | Vráti iterátor nad prvkami v tomto fronte. |
| ponuka? (E e) | Vloží zadaný prvok do tohto prioritného frontu. |
| odstrániť? (Objekt o) | Odstráni jednu inštanciu zadaného prvku z tohto frontu, ak je prítomná. |
| odstrániť všetko? (Kolekcia c) | Odstráni všetky prvky tejto kolekcie, ktoré sú tiež obsiahnuté v zadanej kolekcii (voliteľná operácia). |
| removeIf? (Filter predikátov) | Odstráni všetky prvky tejto kolekcie, ktoré spĺňajú daný predikát. |
| keepAll? (Kolekcia c) | Zachová iba prvky v tejto kolekcii, ktoré sú obsiahnuté v zadanej kolekcii (voliteľná operácia). |
| rozdeľovač() | Vytvorí rozdeľovač s oneskorenou väzbou a rýchlym zlyhaním nad prvkami v tomto fronte. |
| toArray() | Vráti pole obsahujúce všetky prvky v tomto fronte. |
| toArray?(T[] a) | Vráti pole obsahujúce všetky prvky v tomto fronte; typ runtime vráteného poľa je typ zadaného poľa. |
Metódy Deklarované v triede java.util.AbstractQueue
| METÓDA | POPIS |
|---|---|
| addAll(Kolekcia c) | Pridá všetky prvky v zadanej kolekcii do tohto frontu. |
| element() | Načíta, ale neodstráni, hlavu tohto frontu. |
| odstrániť () | Načíta a odstráni hlavu tohto frontu. |
Metódy Deklarované v triede java.util.AbstractCollection
| METÓDA | POPIS |
|---|---|
| obsahuje všetko (kolekcia c) | Vráti hodnotu true, ak táto kolekcia obsahuje všetky prvky v zadanej kolekcii. |
| je prázdny() | Vráti hodnotu true, ak táto kolekcia neobsahuje žiadne prvky. |
| natiahnuť() | Vráti reťazcovú reprezentáciu tejto kolekcie. |
Metódy Deklarované v rozhraní java.util.Collection
| METÓDA | POPIS |
|---|---|
| obsahuje všetko (kolekcia c) | Vráti hodnotu true, ak táto kolekcia obsahuje všetky prvky v zadanej kolekcii. |
| rovná sa (Objekt o) | Porovná zadaný objekt s touto kolekciou kvôli rovnosti. |
| hashCode() | Vráti hodnotu hash kódu pre túto kolekciu. |
| je prázdny() | Vráti hodnotu true, ak táto kolekcia neobsahuje žiadne prvky. |
| parallelStream() | Vráti možný paralelný stream s touto kolekciou ako zdrojom. |
| veľkosť () | Vráti počet prvkov v tejto kolekcii. |
| Prúd() | Vráti sekvenčný stream s touto kolekciou ako zdrojom. |
| toArray (generátor IntFunction) | Vráti pole obsahujúce všetky prvky v tejto kolekcii pomocou poskytnutej funkcie generátora na pridelenie vráteného poľa. |
Metódy Deklarované v rozhraní java.util.Queue
| METÓDA | POPIS |
|---|---|
| nahliadnuť () | Načíta, ale neodstráni hlavičku tohto frontu, alebo vráti hodnotu null, ak je tento front prázdny. |
| anketa() | Načíta a odstráni hlavičku tohto frontu alebo vráti hodnotu null, ak je tento front prázdny. |
Aplikácie :
- Implementácia Dijkstrových a Primových algoritmov.
- Maximalizujte súčet poľa po K negáciách
Súvisiace články :
- Trieda Java.util.PriorityQueue v jazyku Java
- Implementujte PriorityQueue prostredníctvom komparátora v jazyku Java