PriorityQueue naudojama, kai objektai turi būti apdorojami pagal prioritetą. Yra žinoma, kad a Eilė vadovaujasi „First-In-First-Out“ algoritmu, tačiau kartais eilės elementus reikia apdoroti pagal prioritetą, tada pradeda veikti „PriorityQueue“.
„PriorityQueue“ yra pagrįsta prioritetų krūva. Prioritetinės eilės elementai užsakomi pagal natūralų eilės tvarką arba eilės sudarymo metu pateiktą Palygintuvą, priklausomai nuo to, koks konstruktorius naudojamas.
Žemiau pateiktoje prioriteto eilėje elementas su didžiausia ASCII reikšme turės didžiausią prioritetą.
Deklaracija:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Klasė įgyvendina Serializuojama , Pakartojama , Kolekcija , Eilė sąsajos.
Keletas svarbius prioritetų eilės taškus yra tokie:
- PriorityQueue neleidžia nulio.
- Negalime sukurti nepalyginamų objektų prioritetinės eilės
- PriorityQueue yra nesusietos eilės.
- Šios eilės antraštė yra mažiausias elementas nurodytos eilės atžvilgiu. Jei keli elementai yra susieti už mažiausią vertę, galva yra vienas iš tų elementų – ryšiai nutraukiami savavališkai.
- Kadangi „PriorityQueue“ nėra apsaugota nuo gijų, „Java“ suteikia „PriorityBlockingQueue“ klasę, kuri įgyvendina „BlockingQueue“ sąsają, skirtą naudoti „Java“ kelių gijų aplinkoje.
- Eilės gavimo operacijos apklausia, pašalina, apžiūri ir elementą pasiekia eilės pradžioje esantį elementą.
- Tai suteikia O(log(n)) laiko pridėjimo ir apklausos metodams.
- Jis paveldi metodus iš AbstractQueue , AbstractCollection , Kolekcija, ir Objektas klasė.
Konstruktoriai:
1. PriorityQueue(): Sukuria „PriorityQueue“ su numatytuoju pradiniu pajėgumu (11), kuri sutvarko elementus pagal natūralią jų tvarką.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (rinkinys c): Sukuria PriorityQueue, kurioje yra nurodytos kolekcijos elementai.
PriorityQueue pq = new PriorityQueue(rinkinys c);
3. PriorityQueue (tarp pradinė talpa) : Sukuria pirmumo eilę su nurodyta pradine talpa, kuri sutvarko elementus pagal jų natūralią tvarką.
PriorityQueue pq = new PriorityQueue(int pradinė talpa);
4. PriorityQueue (tarp pradinė talpa, palyginimo priemonė): Sukuria PriorityQueue su nurodyta pradine talpa, kuri sutvarko savo elementus pagal nurodytą lyginamąjį elementą.
PriorityQueue pq = new PriorityQueue(int pradinė talpa, palyginimo priemonė);
5. PriorityQueue(PriorityQueue c) : Sukuria PriorityQueue, kurioje yra nurodytos prioritetinės eilės elementai.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue (surūšiuotas rinkinys c) : Sukuria „PriorityQueue“, kurioje yra nurodyto surūšiuoto rinkinio elementai.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue (palyginimo priemonė): Sukuria PriorityQueue su numatytuoju pradiniu pajėgumu ir kurios elementai yra išdėstyti pagal nurodytą lyginamąjį elementą.
PriorityQueue pq = new PriorityQueue(Comparator c);
Pavyzdys:
Toliau pateiktame pavyzdyje paaiškinamos šios pagrindinės prioritetinės eilės operacijos.
„Java“ pavadinimų suteikimo taisyklė
- loginis add(E elementas): Šis metodas įterpia nurodytą elementą į šią prioriteto eilę.
- public peek (): Šis metodas nuskaito, bet nepašalina šios eilės galvos arba grąžina nullą, jei ši eilė tuščia.
- viešoji apklausa (): Šis metodas nuskaito ir pašalina šios eilės galvą arba grąžina nullą, jei ši eilė tuščia.
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());> >}> }> |
>
>Išvestis
10 10 15>
Operacijos PriorityQueue
Pažiūrėkime, kaip atlikti keletą dažnai naudojamų operacijų „Priority Queue“ klasėje.
1. Elementų pridėjimas: Norėdami įtraukti elementą į prioritetinę eilę, galime naudoti add() metodą. PriorityQueue įterpimo tvarka neišsaugoma. Elementai saugomi pagal prioriteto tvarką, kuri pagal numatytuosius nustatymus yra didėjanti.
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);> >}> }> |
>
>Išvestis
[0, 1, 1, 1, 2, 1]>
Surūšiuotų elementų negausime spausdindami 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);> >}> }> |
>
>Išvestis
[For, Geeks, Geeks]>
2. Elementų pašalinimas: Norėdami pašalinti elementą iš prioritetinės eilės, galime naudoti pašalinimo () metodą. Jei tokių objektų yra keli, tada pirmasis objekto įvykis pašalinamas. Be to, norint nuimti galvą ir ją grąžinti, taip pat naudojamas poll() metodas.
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);> >}> }> |
>
>Išvestis
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Prieiga prie elementų: Kadangi eilė vadovaujasi principu First In First Out, galime pasiekti tik eilės galvą. Norėdami pasiekti elementus iš prioritetinės eilės, galime naudoti peek() metodą.
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);> >}> }> |
>
>Išvestis
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. PriorityQueue kartojimas: Yra keletas būdų, kaip kartoti „PriorityQueue“. Garsiausias būdas yra konvertuoti eilę į masyvą ir pereiti naudojant for kilpą. Tačiau eilėje taip pat yra integruotas iteratorius, kurį galima naudoti eilėje kartoti.
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() +>' '>);> >}> >}> }> |
>
>Išvestis
For Geeks Geeks>
Pavyzdys:
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());> >}> }> |
>
>Išvestis
tojson java
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>
Realaus laiko pavyzdžiai:
Prioritetinė eilė yra duomenų struktūra, kurioje elementai yra išdėstyti pagal prioritetą, o aukščiausio prioriteto elementai rodomi eilės priekyje. Štai keletas realių pavyzdžių, kur galima naudoti prioritetines eiles:
- Užduočių planavimas : operacinėse sistemose prioritetinės eilės naudojamos užduotims planuoti pagal jų prioritetų lygius. Pavyzdžiui, aukšto prioriteto užduotis, pvz., kritinis sistemos naujinimas, gali būti suplanuota prieš žemesnio prioriteto užduotį, pvz., fono atsarginės kopijos kūrimo procesą. Skubios pagalbos kambarys: ligoninės skubios pagalbos skyriuje pacientai tiriami atsižvelgiant į jų būklės sunkumą, pirmiausia gydomi tie, kurių būklė yra kritinė. Prioritetinė eilė gali būti naudojama norint tvarkyti pacientų priėmimo pas gydytojus ir slaugytojus tvarką. Tinklo maršrutas: kompiuterių tinkluose prioritetinės eilės naudojamos duomenų paketų srautui valdyti. Aukšto prioriteto paketams, pvz., balso ir vaizdo duomenims, gali būti teikiama pirmenybė žemesnio prioriteto duomenims, pvz., el. pašto ir failų perdavimui. Transportas : Eismo valdymo sistemose eismo srautui valdyti galima naudoti prioritetines eiles. Pavyzdžiui, greitosios pagalbos automobiliams, pvz., greitosios pagalbos automobiliams, gali būti teikiama pirmenybė prieš kitas transporto priemones, siekiant užtikrinti, kad jos galėtų greitai pasiekti tikslą. Užduočių planavimas: užduočių planavimo sistemose prioritetinės eilės gali būti naudojamos užduočių vykdymo tvarkai valdyti. Aukšto prioriteto darbai, pvz., svarbūs sistemos naujinimai, gali būti suplanuoti anksčiau nei žemesnio prioriteto darbai, pvz., duomenų atsarginės kopijos. Internetinės prekyvietės : internetinėse prekyvietėse pirmumo eilės gali būti naudojamos produktų pristatymui klientams valdyti. Didelio prioriteto užsakymams, pvz., skubiam siuntimui, gali būti teikiama pirmenybė prieš standartinius pristatymo užsakymus.
Apskritai prioritetinės eilės yra naudinga duomenų struktūra, skirta valdyti užduotis ir išteklius pagal jų prioritetų lygius įvairiuose realaus pasaulio scenarijuose.
Metodai PriorityQueue klasėje
| METODAS | APIBŪDINIMAS |
|---|---|
| pridėti (ir ir) | Į šią prioritetinę eilę įterpia nurodytą elementą. |
| aišku () | Pašalina visus elementus iš šios prioritetinės eilės. |
| lyginamoji priemonė () | Grąžina lyginamąjį elementą, naudojamą šios eilės elementams rūšiuoti, arba nulį, jei ši eilė rūšiuojama pagal natūralią elementų tvarką. |
| yra? (O objektas) | Grąžina true, jei šioje eilėje yra nurodytas elementas. |
| už kiekvieną? (vartotojo veiksmas) | Atlieka nurodytą veiksmą kiekvienam Iterable elementui, kol visi elementai bus apdoroti arba veiksmas padarys išimtį. |
| iteratorius () | Grąžina šios eilės elementų iteratorių. |
| pasiūlyti? (E e) | Į šią prioritetinę eilę įterpia nurodytą elementą. |
| pašalinti? (O objektas) | Pašalina vieną nurodyto elemento egzempliorių iš šios eilės, jei jis yra. |
| pašalinti viską? (C rinkinys) | Pašalina visus šios kolekcijos elementus, kurie taip pat yra nurodytoje kolekcijoje (pasirenkama operacija). |
| RemoveIf? (Predikatinis filtras) | Pašalina visus šio rinkinio elementus, kurie atitinka nurodytą predikatą. |
| išlaikyti viską? (C rinkinys) | Išsaugo tik šio rinkinio elementus, kurie yra nurodytoje kolekcijoje (pasirenkama operacija). |
| skirstytuvas () | Sukuria vėlai susiejantį ir greitą skirstytuvą virš šios eilės elementų. |
| toArray () | Grąžina masyvą, kuriame yra visi šios eilės elementai. |
| to Array? (T[] a) | Grąžina masyvą, kuriame yra visi šios eilės elementai; grąžinamo masyvo vykdymo laikas yra nurodyto masyvo tipas. |
Metodai, deklaruoti klasėje java.util.AbstractQueue
| METODAS | APIBŪDINIMAS |
|---|---|
| pridėti viską (rinkinys c) | Į šią eilę įtraukiami visi nurodytos kolekcijos elementai. |
| elementas () | Nuskaito, bet nepašalina šios eilės viršūnės. |
| pašalinti () | Nuskaito ir pašalina šios eilės galvą. |
Metodai, paskelbti klasėje java.util.AbstractCollection
| METODAS | APIBŪDINIMAS |
|---|---|
| yra viskas (rinkinys c) | Grąžina true, jei šioje kolekcijoje yra visi nurodytos kolekcijos elementai. |
| Yra tuščias() | Grąžina tiesa, jei šioje kolekcijoje nėra elementų. |
| toString() | Pateikia šios kolekcijos eilutės atvaizdavimą. |
Metodai, paskelbti sąsajoje java.util.Collection
| METODAS | APIBŪDINIMAS |
|---|---|
| yra viskas (rinkinys c) | Grąžina true, jei šioje kolekcijoje yra visi nurodytos kolekcijos elementai. |
| lygus (O objektas) | Lygina nurodytą objektą su šia kolekcija, kad būtų lygybė. |
| maišos kodas () | Grąžina šio rinkinio maišos kodo reikšmę. |
| Yra tuščias() | Grąžina tiesa, jei šioje kolekcijoje nėra elementų. |
| parallelStream() | Pateikiamas galbūt lygiagretus srautas, kurio šaltinis yra ši kolekcija. |
| dydis () | Grąžina elementų skaičių šioje kolekcijoje. |
| srautas() | Pateikia nuoseklų srautą, kurio šaltinis yra ši kolekcija. |
| toArray (IntFunction generatorius) | Grąžina masyvą, kuriame yra visi šios kolekcijos elementai, naudojant pateiktą generatoriaus funkciją grąžintam masyvui paskirstyti. |
Metodai, paskelbti sąsajoje java.util.Queue
| METODAS | APIBŪDINIMAS |
|---|---|
| žvilgtelėti () | Nuskaito, bet nepašalina šios eilės antraštės arba grąžina nulį, jei ši eilė tuščia. |
| apklausa () | Nuskaito ir pašalina šios eilės antraštę arba grąžina nulį, jei ši eilė tuščia. |
Programos :
- Dijkstra ir Prim algoritmų įgyvendinimas.
- Padidinti masyvo sumą po K neigimo
susiję straipsniai :
- Java.util.PriorityQueue klasė Java
- Įdiekite „PriorityQueue“ naudodami „Comparator“ programoje „Java“.