PriorityQueue se uporablja, ko naj bi se objekti obdelali na podlagi prioritete. Znano je, da je a Čakalna vrsta sledi algoritmu First-In-First-Out, včasih pa je treba elemente čakalne vrste obdelati glede na prioriteto, takrat pride v poštev PriorityQueue.
PriorityQueue temelji na prednostni kopici. Elementi prednostne čakalne vrste so razvrščeni v skladu z naravnim vrstnim redom ali s primerjalnikom, ki je na voljo v času gradnje čakalne vrste, odvisno od uporabljenega konstruktorja.
V spodnji prednostni čakalni vrsti bo imel najvišjo prednost element z najvišjo vrednostjo ASCII.
Izjava:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Razred izvaja Serializable , Ponovljivo , Zbirka , Čakalna vrsta vmesniki.
Nekaj pomembne točke v prednostni čakalni vrsti so naslednji:
- PriorityQueue ne dovoljuje ničelne vrednosti.
- Ne moremo ustvariti PriorityQueue predmetov, ki niso primerljivi
- PriorityQueue so nevezane čakalne vrste.
- Glava te čakalne vrste je najmanjši element glede na navedeni vrstni red. Če je več elementov izenačenih za najmanjšo vrednost, je glava eden od teh elementov – vezi se poljubno prekinejo.
- Ker PriorityQueue ni varen za niti, java ponuja razred PriorityBlockingQueue, ki implementira vmesnik BlockingQueue za uporabo v večnitnem okolju Java.
- Operacije pridobivanja čakalne vrste anketirajo, odstranijo, pokukajo in element dostopajo do elementa na čelu čakalne vrste.
- Zagotavlja O(log(n)) časa za metode dodajanja in glasovanja.
- Podeduje metode od AbstractQueue , AbstractCollection , zbirka, in Objekt razred.
Konstruktorji:
1. PriorityQueue(): Ustvari PriorityQueue s privzeto začetno zmogljivostjo (11), ki svoje elemente razvrsti glede na njihov naravni vrstni red.
PriorityQueue pq = nova PriorityQueue();
2. PriorityQueue (zbirka c): Ustvari PriorityQueue, ki vsebuje elemente v navedeni zbirki.
PriorityQueue pq = nova PriorityQueue(Zbirka c);
3. PriorityQueue(int initialCapacity) : ustvari PriorityQueue z določeno začetno zmogljivostjo, ki razvrsti svoje elemente glede na njihov naravni vrstni red.
PriorityQueue pq = nova PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, Comparator comparator): Ustvari PriorityQueue z določeno začetno zmogljivostjo, ki razvrsti svoje elemente glede na podani primerjalnik.
PriorityQueue pq = nova PriorityQueue(int initialCapacity, Comparator comparator);
5. PriorityQueue(PriorityQueue c) : ustvari PriorityQueue, ki vsebuje elemente v določeni prednostni čakalni vrsti.
PriorityQueue pq = nova PriorityQueue(PriorityQueue c);
6. PriorityQueue(SortedSet c) : ustvari PriorityQueue, ki vsebuje elemente v podanem razvrščenem nizu.
PriorityQueue pq = nova PriorityQueue(SortedSet c);
7. PriorityQueue (primerjalni primerjalnik): Ustvari PriorityQueue s privzeto začetno zmogljivostjo in katere elementi so urejeni glede na podani primerjalnik.
PriorityQueue pq = nova PriorityQueue(Comparator c);
primer:
Spodnji primer pojasnjuje naslednje osnovne operacije prednostne čakalne vrste.
imenik v ukazih linux
- boolean add(E element): ta metoda vstavi podani element v to prioritetno čakalno vrsto.
- public peek(): ta metoda pridobi glavo te čakalne vrste, vendar ne odstrani, ali vrne nič, če je ta čakalna vrsta prazna.
- public poll(): Ta metoda pridobi in odstrani glavo te čakalne vrste ali vrne ničelno vrednost, če je ta čakalna vrsta prazna.
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());> >}> }> |
>
>Izhod
10 10 15>
Operacije na PriorityQueue
Poglejmo, kako izvesti nekaj pogosto uporabljenih operacij v razredu prednostne čakalne vrste.
1. Dodajanje elementov: Za dodajanje elementa v prednostno čakalno vrsto lahko uporabimo metodo add(). Vrstni red vstavljanja se ne ohrani v PriorityQueue. Elementi so shranjeni na podlagi prednostnega vrstnega reda, ki je privzeto naraščajoč.
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);> >}> }> |
>
>Izhod
[0, 1, 1, 1, 2, 1]>
S tiskanjem PriorityQueue ne bomo dobili razvrščenih elementov.
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);> >}> }> |
>
>Izhod
[For, Geeks, Geeks]>
2. Odstranjevanje elementov: Za odstranitev elementa iz prednostne čakalne vrste lahko uporabimo metodo remove(). Če je takšnih objektov več, se prvi pojavitev predmeta odstrani. Poleg tega se metoda poll() uporablja tudi za odstranitev glave in njeno vrnitev.
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);> >}> }> |
>
>Izhod
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Dostop do elementov: Ker Queue sledi načelu First In First Out, lahko dostopamo le do glave čakalne vrste. Za dostop do elementov iz prednostne čakalne vrste lahko uporabimo metodo 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);> >}> }> |
>
>Izhod
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Ponavljanje PriorityQueue: Obstaja več načinov za ponavljanje skozi PriorityQueue. Najbolj znan način je pretvorba čakalne vrste v matriko in prečkanje z uporabo zanke for. Vendar pa ima čakalna vrsta tudi vgrajen iterator, ki se lahko uporablja za ponavljanje skozi čakalno vrsto.
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() +>' '>);> >}> >}> }> |
>
>
java za vrste zankIzhod
For Geeks Geeks>
primer:
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());> >}> }> |
>
>Izhod
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>
Primeri v realnem času:
Prednostna čakalna vrsta je podatkovna struktura, v kateri so elementi razvrščeni po prioriteti, pri čemer so elementi z najvišjo prioriteto prikazani na začetku čakalne vrste. Tukaj je nekaj primerov iz resničnega sveta, kjer je mogoče uporabiti prednostne čakalne vrste:
- Razporejanje opravil : V operacijskih sistemih se prednostne čakalne vrste uporabljajo za razporejanje opravil glede na njihove prioritetne ravni. Na primer, naloga z visoko prioriteto, kot je kritična posodobitev sistema, je lahko načrtovana pred nalogo z nižjo prioriteto, kot je postopek varnostnega kopiranja v ozadju. Urgenca: V bolnišnični urgenci se bolniki triažirajo glede na resnost njihovega stanja, pri čemer se najprej zdravijo tisti v kritičnem stanju. Prednostno čakalno vrsto je mogoče uporabiti za upravljanje vrstnega reda, v katerem bolnike pregledajo zdravniki in medicinske sestre. Omrežno usmerjanje : V računalniških omrežjih se za upravljanje pretoka podatkovnih paketov uporabljajo prednostne čakalne vrste. Paketi z visoko prioriteto, kot so glasovni in video podatki, imajo lahko prednost pred podatki z nižjo prioriteto, kot so e-pošta in prenosi datotek. Prevoz : V sistemih za upravljanje prometa se lahko prednostne čakalne vrste uporabljajo za upravljanje prometnega toka. Na primer, vozila za nujne primere, kot so reševalna vozila, imajo lahko prednost pred drugimi vozili, da lahko hitro dosežejo cilj. Razporejanje opravil : V sistemih za razporejanje opravil se lahko prednostne čakalne vrste uporabljajo za upravljanje vrstnega reda, v katerem se opravila izvajajo. Opravila z visoko prioriteto, kot so kritične posodobitve sistema, so lahko načrtovana pred opravili z nižjo prioriteto, kot je varnostno kopiranje podatkov. Spletne tržnice : Na spletnih tržnicah je mogoče prednostne čakalne vrste uporabiti za upravljanje dostave izdelkov strankam. Naročila z visoko prioriteto, kot je ekspresno pošiljanje, imajo lahko prednost pred standardnimi naročili za pošiljanje.
Na splošno so prednostne čakalne vrste uporabna podatkovna struktura za upravljanje nalog in virov na podlagi njihovih prioritetnih ravni v različnih realnih scenarijih.
Metode v razredu PriorityQueue
| METODA | OPIS |
|---|---|
| dodaj (in in) | Vstavi podani element v to prednostno čakalno vrsto. |
| počisti() | Odstrani vse elemente iz te prednostne čakalne vrste. |
| primerjalnik() | Vrne primerjalnik, uporabljen za razvrščanje elementov v tej čakalni vrsti, ali vrednost null, če je ta čakalna vrsta razvrščena glede na naravni vrstni red svojih elementov. |
| vsebuje? (predmet o) | Vrne true, če ta čakalna vrsta vsebuje navedeni element. |
| forEach? (ukrep potrošnika) | Izvede dano dejanje za vsak element Iterable, dokler niso vsi elementi obdelani ali dejanje vrže izjemo. |
| iterator() | Vrne iterator nad elementi v tej čakalni vrsti. |
| ponudba? (E e) | Vstavi podani element v to prednostno čakalno vrsto. |
| odstraniti? (Predmet o) | Odstrani en primerek navedenega elementa iz te čakalne vrste, če je prisoten. |
| odstraniti vse? (zbirka c) | Odstrani vse elemente te zbirke, ki jih vsebuje tudi navedena zbirka (izbirna operacija). |
| removeIf? (Predikatni filter) | Odstrani vse elemente te zbirke, ki izpolnjujejo dani predikat. |
| retainAll? (Zbirka c) | Ohrani le elemente v tej zbirki, ki so vsebovani v navedeni zbirki (izbirna operacija). |
| spliterator() | Ustvari pozno povezovalni in neuspešno hiter razdelilnik nad elementi v tej čakalni vrsti. |
| toArray() | Vrne matriko, ki vsebuje vse elemente v tej čakalni vrsti. |
| toArray?(T[] a) | Vrne matriko, ki vsebuje vse elemente v tej čakalni vrsti; vrsta izvajalnega časa vrnjene matrike je navedena matrika. |
Metode, deklarirane v razredu java.util.AbstractQueue
| METODA | OPIS |
|---|---|
| addAll(zbirka c) | V to čakalno vrsto doda vse elemente v navedeni zbirki. |
| element() | Pridobi, vendar ne odstrani glave te čakalne vrste. |
| Odstrani() | Pridobi in odstrani glavo te čakalne vrste. |
Metode, deklarirane v razredu java.util.AbstractCollection
| METODA | OPIS |
|---|---|
| vsebujeVse(Zbirka c) | Vrne true, če ta zbirka vsebuje vse elemente v navedeni zbirki. |
| je prazno() | Vrne true, če ta zbirka ne vsebuje elementov. |
| toString() | Vrne predstavitev niza te zbirke. |
Metode, deklarirane v vmesniku java.util.Collection
| METODA | OPIS |
|---|---|
| vsebujeVse(Zbirka c) | Vrne true, če ta zbirka vsebuje vse elemente v navedeni zbirki. |
| je enako (predmet o) | Primerja navedeni predmet s to zbirko za enakost. |
| hashCode() | Vrne vrednost zgoščene kode za to zbirko. |
| je prazno() | Vrne true, če ta zbirka ne vsebuje elementov. |
| parallelStream() | Vrne morebitni vzporedni tok s to zbirko kot virom. |
| velikost () | Vrne število elementov v tej zbirki. |
| tok () | Vrne zaporedni tok s to zbirko kot izvorom. |
| toArray(generator IntFunction) | Vrne matriko, ki vsebuje vse elemente v tej zbirki, z uporabo ponujene funkcije generatorja za dodelitev vrnjene matrike. |
Metode, deklarirane v vmesniku java.util.Queue
| METODA | OPIS |
|---|---|
| pokukati() | Pridobi, vendar ne odstrani glave te čakalne vrste ali vrne ničelno vrednost, če je ta čakalna vrsta prazna. |
| anketa() | Pridobi in odstrani glavo te čakalne vrste ali vrne ničelno vrednost, če je ta čakalna vrsta prazna. |
Aplikacije :
- Implementacija Dijkstrinih in Primovih algoritmov.
- Maksimiraj vsoto matrike po K negacij
povezani članki :
- Razred Java.util.PriorityQueue v Javi
- Implementirajte PriorityQueue prek primerjalnika v Javi