PriorityQueuea käytetään, kun objektit on tarkoitus käsitellä prioriteetin perusteella. Tiedetään, että a Jonottaa noudattaa First-In-First-Out-algoritmia, mutta joskus jonon elementit on käsiteltävä prioriteetin mukaan, jolloin PriorityQueue tulee peliin.
PriorityQueue perustuu prioriteettikekoon. Prioriteettijonon elementit järjestetään luonnollisen järjestyksen mukaan tai jonon rakennusaikana toimitetulla Comparatorilla riippuen siitä, kumpaa rakentajaa käytetään.
Alla olevassa prioriteettijonossa elementillä, jolla on suurin ASCII-arvo, on korkein prioriteetti.
Ilmoitus:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Luokka toteuttaa Sarjasoitavissa , Iteroitavissa , Kokoelma , Jonottaa käyttöliittymät.
Muutama tärkeitä kohtia prioriteettijonossa ovat seuraavat:
- PriorityQueue ei salli nollaa.
- Emme voi luoda PriorityQueue-objekteja, jotka eivät ole vertailukelpoisia
- PriorityQueue ovat sitomattomia jonoja.
- Tämän jonon pää on vähiten elementti määritettyyn järjestykseen nähden. Jos useat elementit on sidottu pienimpään arvoon, pää on yksi näistä elementeistä – siteet katkeavat mielivaltaisesti.
- Koska PriorityQueue ei ole säikeen turvallinen, java tarjoaa PriorityBlockingQueue-luokan, joka toteuttaa BlockingQueue-rajapinnan käytettäväksi Java-monisäikeisessä ympäristössä.
- Jonon hakutoiminnot pollaavat, poistavat, kurkistavat ja käyttävät elementtiä jonon kärjessä.
- Se tarjoaa O(log(n))-ajan lisäys- ja kyselymenetelmille.
- Se perii menetelmät AbstractQueue , AbstractCollection , Kokoelma, ja Esine luokkaa.
Rakentajat:
1. PriorityQueue(): Luo PriorityQueuen oletusalkukapasiteetilla (11), joka järjestää elementit niiden luonnollisen järjestyksen mukaan.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue(kokoelma c): Luo PriorityQueuen, joka sisältää määritetyn kokoelman elementit.
PriorityQueue pq = new PriorityQueue(kokoelma c);
3. PriorityQueue(int alkuperäinen kapasiteetti) : Luo PriorityQueuen määritetyllä alkukapasiteetilla, joka järjestää elementit niiden luonnollisen järjestyksen mukaan.
PriorityQueue pq = new PriorityQueue(int alkuperäinen kapasiteetti);
4. PriorityQueue(int alkuperäinen kapasiteetti, vertailijan vertailija): Luo PriorityQueuen määritetyllä alkukapasiteetilla, joka järjestää elementit määritetyn vertailijan mukaan.
PriorityQueue pq = new PriorityQueue(int alkuperäinen kapasiteetti, Comparator komparaattori);
5. PriorityQueue(PriorityQueue c) : Luo PriorityQueuen, joka sisältää määritetyn prioriteettijonon elementit.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue (lajiteltujoukko c) : Luo PriorityQueuen, joka sisältää määritetyn lajitellun joukon elementit.
PriorityQueue pq = uusi PriorityQueue(SortedSet c);
7. PriorityQueue (vertailija): Luo PriorityQueuen, jolla on oletusarvoinen alkukapasiteetti ja jonka elementit on järjestetty määritetyn vertailijan mukaan.
PriorityQueue pq = new PriorityQueue(Comparator c);
Esimerkki:
Alla oleva esimerkki selittää seuraavat prioriteettijonon perustoiminnot.
tiikerileijonan ero
- boolean add(E-elementti): Tämä menetelmä lisää määritetyn elementin tähän prioriteettijonoon.
- public peek(): Tämä menetelmä hakee, mutta ei poista, tämän jonon pään tai palauttaa nolla-arvon, jos tämä jono on tyhjä.
- public poll(): Tämä menetelmä hakee ja poistaa tämän jonon pään tai palauttaa nolla-arvon, jos tämä jono on tyhjä.
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());> >}> }> |
>
>Lähtö
10 10 15>
Toiminnot PriorityQueuessa
Katsotaanpa, kuinka suoritetaan muutama usein käytetty toiminto Priority Queue -luokassa.
1. Elementtien lisääminen: Elementin lisäämiseksi prioriteettijonoon voimme käyttää add()-menetelmää. Lisäysjärjestystä ei säilytetä PriorityQueuessa. Elementit tallennetaan prioriteettijärjestyksen mukaan, joka on oletusarvoisesti nouseva.
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);> >}> }> |
>
>Lähtö
[0, 1, 1, 1, 2, 1]>
Emme saa lajiteltuja elementtejä tulostamalla 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);> >}> }> |
>
>Lähtö
[For, Geeks, Geeks]>
2. Elementtien poistaminen: Elementin poistamiseksi prioriteettijonosta voimme käyttää remove()-menetelmää. Jos tällaisia objekteja on useita, objektin ensimmäinen esiintyminen poistetaan. Tämän lisäksi poll()-menetelmää käytetään myös pään poistamiseen ja palauttamiseen.
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);> >}> }> |
>
>Lähtö
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Elementtien käyttö: Koska Queue noudattaa First In First Out -periaatetta, voimme käyttää vain jonon päätä. Voidaksemme käyttää elementtejä prioriteettijonosta, voimme käyttää peek()-menetelmää.
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);> >}> }> |
>
>Lähtö
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. PriorityQueuen toistaminen: PriorityQueuessa on useita tapoja iteroida. Tunnetuin tapa on muuntaa jono taulukoksi ja kulkea for-silmukan avulla. Jonossa on kuitenkin myös sisäänrakennettu iteraattori, jonka avulla voidaan iteroida jonon läpi.
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() +>' '>);> >}> >}> }> |
myivecricket vaihtoehto
>
>Lähtö
For Geeks Geeks>
Esimerkki:
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());> >}> }> |
>
>Lähtö
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>
Reaaliaikaisia esimerkkejä:
Priority Queue on tietorakenne, jossa elementit on järjestetty prioriteetin mukaan ja korkeimman prioriteetin elementit näkyvät jonon etuosassa. Tässä on joitain todellisia esimerkkejä siitä, missä prioriteettijonoja voidaan käyttää:
- Tehtävien ajoitus: Käyttöjärjestelmissä prioriteettijonoja käytetään tehtävien ajoittamiseen niiden prioriteettitasojen perusteella. Esimerkiksi korkean prioriteetin tehtävä, kuten kriittinen järjestelmäpäivitys, voidaan ajoittaa ennen alemman prioriteetin tehtävää, kuten taustavarmuuskopiointiprosessia. Päivystys: Sairaalan päivystyspoliklinikalla potilaat tutkitaan heidän tilansa vakavuuden perusteella, ja kriittisessä tilassa olevat hoidetaan ensin. Prioriteettijonon avulla voidaan hallita potilaiden vastaanottojärjestystä lääkäreiden ja sairaanhoitajien luona. Verkkoreititys: Tietokoneverkoissa prioriteettijonoja käytetään tietopakettien virran hallintaan. Korkean prioriteetin paketit, kuten ääni- ja videodata, voidaan antaa etusijalle alemman prioriteetin dataan, kuten sähköpostiin ja tiedostojen siirtoihin, nähden. Liikenne: Liikenteenhallintajärjestelmissä prioriteettijonoja voidaan käyttää liikenteen hallinnassa. Esimerkiksi hätäajoneuvot, kuten ambulanssit, voidaan antaa etusijalle muihin ajoneuvoihin nähden, jotta ne voivat saavuttaa määränpäänsä nopeasti. Työn ajoitus: Töiden ajoitusjärjestelmissä prioriteettijonoja voidaan käyttää töiden suoritusjärjestyksen hallintaan. Korkean prioriteetin työt, kuten kriittiset järjestelmäpäivitykset, voidaan ajoittaa ennen alemman prioriteetin töitä, kuten tietojen varmuuskopiointia. Online-markkinapaikat : Online-markkinapaikoilla prioriteettijonoja voidaan käyttää tuotteiden toimittamisen hallintaan asiakkaille. Korkean prioriteetin tilaukset, kuten pikalähetys, voidaan antaa etusijalle tavallisiin toimitustilauksiin nähden.
Kaiken kaikkiaan prioriteettijonot ovat hyödyllinen tietorakenne tehtävien ja resurssien hallintaan niiden prioriteettitasojen perusteella erilaisissa reaalimaailman skenaarioissa.
Menetelmät PriorityQueue-luokassa
| MENETELMÄ | KUVAUS |
|---|---|
| lisää (ja ja) | Lisää määritetyn elementin tähän prioriteettijonoon. |
| asia selvä() | Poistaa kaikki elementit tästä prioriteettijonosta. |
| vertailija() | Palauttaa vertailijan, jota käytetään tämän jonon elementtien järjestämiseen, tai nollan, jos tämä jono on lajiteltu elementtien luonnollisen järjestyksen mukaan. |
| sisältää? (Objekti o) | Palauttaa tosi, jos tämä jono sisältää määritetyn elementin. |
| jokaiselle? (kuluttajan toiminta) | Suorittaa annetun toiminnon kullekin iterable-elementille, kunnes kaikki elementit on käsitelty tai toiminto tekee poikkeuksen. |
| iteraattori() | Palauttaa iteraattorin tämän jonon elementtien päälle. |
| tarjota? (E) | Lisää määritetyn elementin tähän prioriteettijonoon. |
| poistaa? (Objekti o) | Poistaa määritetyn elementin yksittäisen esiintymän tästä jonosta, jos se on olemassa. |
| poistaa kaikki? (kokoelma c) | Poistaa kaikki tämän kokoelman elementit, jotka myös sisältyvät määritettyyn kokoelmaan (valinnainen toiminto). |
| Poista Jos? (Predikaattisuodatin) | Poistaa kaikki tämän kokoelman elementit, jotka täyttävät annetun predikaatin. |
| säilyttää kaikki? (kokoelma c) | Säilyttää vain tämän kokoelman elementit, jotka sisältyvät määritettyyn kokoelmaan (valinnainen toiminto). |
| splitter() | Luo myöhään sitovan ja nopean jakajan tämän jonon elementtien päälle. |
| toArray() | Palauttaa taulukon, joka sisältää kaikki tämän jonon elementit. |
| toArray?(T[] a) | Palauttaa taulukon, joka sisältää kaikki tämän jonon elementit; palautetun taulukon ajonaikainen tyyppi on määritetyn taulukon tyyppi. |
Luokassa java.util.AbstractQueue ilmoitetut menetelmät
| MENETELMÄ | KUVAUS |
|---|---|
| lisää kaikki (kokoelma c) | Lisää kaikki määritetyn kokoelman elementit tähän jonoon. |
| elementti() | Hakee tämän jonon pään, mutta ei poista sitä. |
| Poista() | Hakee ja poistaa tämän jonon pään. |
Luokassa java.util.AbstractCollection ilmoitetut menetelmät
| MENETELMÄ | KUVAUS |
|---|---|
| sisältääKaikki (kokoelma c) | Palauttaa tosi, jos tämä kokoelma sisältää kaikki määritetyn kokoelman elementit. |
| on tyhjä() | Palauttaa tosi, jos tämä kokoelma ei sisällä elementtejä. |
| toString() | Palauttaa tämän kokoelman merkkijonoesityksen. |
Käyttöliittymässä java.util.Collection ilmoitetut menetelmät
| MENETELMÄ | KUVAUS |
|---|---|
| sisältääKaikki (kokoelma c) | Palauttaa tosi, jos tämä kokoelma sisältää kaikki määritetyn kokoelman elementit. |
| yhtä suuri (objekti o) | Vertaa määritettyä objektia tähän kokoelmaan tasa-arvon vuoksi. |
| hash koodin() | Palauttaa tämän kokoelman hash-koodin arvon. |
| on tyhjä() | Palauttaa tosi, jos tämä kokoelma ei sisällä elementtejä. |
| parallelStream() | Palauttaa mahdollisesti rinnakkaisen streamin, jonka lähteenä on tämä kokoelma. |
| koko() | Palauttaa tämän kokoelman elementtien määrän. |
| stream() | Palauttaa peräkkäisen streamin, jonka lähteenä on tämä kokoelma. |
| toArray (IntFunction-generaattori) | Palauttaa taulukon, joka sisältää kaikki tämän kokoelman elementit, käyttämällä palautetun taulukon varaamiseen toimitettua generaattoritoimintoa. |
Menetelmät Ilmoitettu käyttöliittymässä java.util.Queue
| MENETELMÄ | KUVAUS |
|---|---|
| kurkistaa() | Hakee, mutta ei poista, tämän jonon pään tai palauttaa nolla-arvon, jos tämä jono on tyhjä. |
| kysely () | Hakee ja poistaa tämän jonon pään tai palauttaa nollan, jos tämä jono on tyhjä. |
Sovellukset :
- Dijkstran ja Primin algoritmien käyttöönotto.
- Maksimoi taulukon summa K negation jälkeen
Aiheeseen liittyvät artikkelit :
- Java.util.PriorityQueue-luokka Javassa
- Toteuta PriorityQueue Comparatorin kautta Javassa