O PriorityQueue este utilizată atunci când obiectele ar trebui să fie procesate pe baza priorității. Se știe că a Coadă urmează algoritmul First-In-First-Out, dar uneori elementele cozii sunt necesare pentru a fi procesate în funcție de prioritate, atunci intră în joc PriorityQueue.
PriorityQueue se bazează pe heap-ul prioritar. Elementele cozii de prioritate sunt ordonate conform ordonării firești, sau printr-un Comparator pus la dispoziție la momentul construirii cozii, în funcție de constructorul utilizat.
În coada de prioritate de mai jos, un element cu o valoare ASCII maximă va avea cea mai mare prioritate.
Declaraţie:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Clasa implementează Serializabil , Iterabil , Colectie , Coadă interfețe.
Câțiva puncte importante din Coada de prioritate sunt după cum urmează:
- PriorityQueue nu permite null.
- Nu putem crea un PriorityQueue de obiecte care nu sunt comparabile
- PriorityQueue sunt cozi nelegate.
- Capul acestei cozi este cel mai mic element în raport cu ordinea specificată. Dacă mai multe elemente sunt legate pentru cea mai mică valoare, capul este unul dintre aceste elemente - legăturile sunt rupte arbitrar.
- Deoarece PriorityQueue nu este sigură pentru fire, java oferă clasa PriorityBlockingQueue care implementează interfața BlockingQueue pentru a fi utilizată într-un mediu java multithreading.
- Operațiunile de recuperare a cozii interogează, șterg, peek și accesează elementul din capul cozii.
- Oferă timp O(log(n)) pentru metodele de adăugare și sondare.
- Moștenește metode de la AbstractQueue , Colecția de abstracte , Colectie, și Obiect clasă.
Constructori:
1. PriorityQueue(): Creează o PriorityQueue cu capacitatea inițială implicită (11) care își ordonează elementele în funcție de ordonarea lor naturală.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue(Colecția c): Creează un PriorityQueue care conține elementele din colecția specificată.
PriorityQueue pq = new PriorityQueue(Colecție c);
3. PriorityQueue(int initialCapacity) : creează o PriorityQueue cu capacitatea inițială specificată care își ordonează elementele în funcție de ordonarea lor naturală.
PriorityQueue pq = new PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, comparator comparator): Creează o PriorityQueue cu capacitatea inițială specificată care își ordonează elementele conform comparatorului specificat.
PriorityQueue pq = new PriorityQueue(int initialCapacity, Comparator comparator);
5. PriorityQueue(PriorityQueue c) : creează o PriorityQueue care conține elementele din coada de prioritate specificată.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue(SortedSet c) : creează o PriorityQueue care conține elementele din setul sortat specificat.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue (comparator de comparație): Creează o PriorityQueue cu capacitatea inițială implicită și ale cărei elemente sunt ordonate conform comparatorului specificat.
PriorityQueue pq = new PriorityQueue(Comparator c);
Exemplu:
Exemplul de mai jos explică următoarele operații de bază ale cozii de prioritate.
program in java
- boolean add(E element): Această metodă inserează elementul specificat în această coadă de prioritate.
- public peek(): Această metodă preia, dar nu elimină, capul acestei cozi sau returnează null dacă această coadă este goală.
- public poll(): Această metodă preia și elimină capul acestei cozi, sau returnează null dacă această coadă este goală.
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());> >}> }> |
>
>Ieșire
10 10 15>
Operații pe PriorityQueue
Să vedem cum să efectuăm câteva operațiuni frecvent utilizate pe clasa Priority Queue.
1. Adăugarea de elemente: Pentru a adăuga un element într-o coadă de prioritate, putem folosi metoda add(). Ordinea de inserare nu este reținută în PriorityQueue. Elementele sunt stocate pe baza ordinii de prioritate care este implicit crescătoare.
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);> >}> }> |
>
>Ieșire
[0, 1, 1, 1, 2, 1]>
Nu vom obține elemente sortate prin imprimarea 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);> >}> }> |
>
porțiune de matrice java
>Ieșire
[For, Geeks, Geeks]>
2. Îndepărtarea elementelor: Pentru a elimina un element dintr-o coadă de prioritate, putem folosi metoda remove(). Dacă există mai multe astfel de obiecte, atunci prima apariție a obiectului este eliminată. În afară de asta, metoda poll() este folosită și pentru a elimina capul și a-l returna.
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);> >}> }> |
>
>Ieșire
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Accesarea elementelor: Deoarece Queue urmează principiul First In First Out, putem accesa doar capul cozii. Pentru a accesa elemente dintr-o coadă de prioritate, putem folosi metoda 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);> >}> }> |
>
>Ieșire
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Repetarea PriorityQueue: Există mai multe moduri de a itera prin PriorityQueue. Cel mai faimos mod este conversia cozii în matrice și parcurgerea folosind bucla for. Cu toate acestea, coada are, de asemenea, un iterator încorporat care poate fi folosit pentru a itera prin coadă.
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() +>' '>);> >}> >}> }> |
>
>Ieșire
For Geeks Geeks>
Exemplu:
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());> >}> }> |
>
>Ieșire
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>
Exemple în timp real:
Priority Queue este o structură de date în care elementele sunt ordonate după prioritate, elementele cu cea mai mare prioritate apărând în partea din față a cozii. Iată câteva exemple reale de unde pot fi folosite cozile prioritare:
- Programarea sarcinilor: În sistemele de operare, cozile de prioritate sunt folosite pentru a programa sarcini pe baza nivelurilor lor de prioritate. De exemplu, o sarcină cu prioritate ridicată, cum ar fi o actualizare critică a sistemului, poate fi programată înaintea unei sarcini cu prioritate mai mică, cum ar fi un proces de backup în fundal. Camera de urgență: într-o cameră de urgență a unui spital, pacienții sunt triați în funcție de severitatea stării lor, cei în stare critică fiind tratați mai întâi. O coadă prioritară poate fi utilizată pentru a gestiona ordinea în care pacienții sunt consultați de medici și asistente. Rutarea rețelei: În rețelele de calculatoare, cozile prioritare sunt folosite pentru a gestiona fluxul de pachete de date. Pachetele cu prioritate ridicată, cum ar fi datele voce și video, pot avea prioritate față de datele cu prioritate mai mică, cum ar fi transferurile de e-mail și fișiere. Transport: În sistemele de management al traficului, cozile prioritare pot fi folosite pentru a gestiona fluxul de trafic. De exemplu, vehiculelor de urgență, cum ar fi ambulanțele, li se poate acorda prioritate față de alte vehicule pentru a se asigura că pot ajunge rapid la destinație. Programare job: În sistemele de programare job, cozile prioritare pot fi folosite pentru a gestiona ordinea în care sunt executate joburile. Lucrările cu prioritate înaltă, cum ar fi actualizările critice ale sistemului, pot fi programate înaintea lucrărilor cu prioritate mai mică, cum ar fi backup-urile de date. Piețe online : în piețele online, cozile prioritare pot fi folosite pentru a gestiona livrarea produselor către clienți. Comenzile cu prioritate ridicată, cum ar fi transportul expres, pot avea prioritate față de comenzile standard de expediere.
În general, cozile de prioritate sunt o structură de date utilă pentru gestionarea sarcinilor și resurselor pe baza nivelurilor lor de prioritate în diferite scenarii din lumea reală.
Metode din clasa PriorityQueue
| METODĂ | DESCRIERE |
|---|---|
| adaugă (și și) | Inserează elementul specificat în această coadă de prioritate. |
| clar() | Elimină toate elementele din această coadă de prioritate. |
| comparator() | Returnează comparatorul folosit pentru a ordona elementele din această coadă, sau null dacă această coadă este sortată în funcție de ordinea naturală a elementelor sale. |
| conține? (Obiectul o) | Returnează adevărat dacă această coadă conține elementul specificat. |
| pentru fiecare? (acțiunea consumatorului) | Efectuează acțiunea dată pentru fiecare element din Iterable până când toate elementele au fost procesate sau acțiunea aruncă o excepție. |
| iterator() | Returnează un iterator peste elementele din această coadă. |
| oferta?(E e) | Inserează elementul specificat în această coadă de prioritate. |
| eliminați? (Obiectul o) | Îndepărtează o singură instanță a elementului specificat din această coadă, dacă este prezentă. |
| removeAll? (Colecția c) | Îndepărtează toate elementele acestei colecții care sunt, de asemenea, conținute în colecția specificată (operație opțională). |
| removeIf? (filtru de predicate) | Îndepărtează toate elementele acestei colecții care satisfac predicatul dat. |
| retainAll? (Colecția c) | Reține numai elementele din această colecție care sunt conținute în colecția specificată (operație opțională). |
| spliterator() | Creează un Spliterator cu legare întârziată și cu eșec rapid peste elementele din această coadă. |
| toArray() | Returnează o matrice care conține toate elementele din această coadă. |
| toArray?(T[] a) | Returnează o matrice care conține toate elementele din această coadă; tipul de rulare al matricei returnate este cel al matricei specificate. |
Metode declarate în clasa java.util.AbstractQueue
| METODĂ | DESCRIERE |
|---|---|
| addAll(Colecția c) | Adaugă toate elementele din colecția specificată la această coadă. |
| element() | Preia, dar nu elimină, capul acestei cozi. |
| elimina() | Preia și elimină capul acestei cozi. |
Metode declarate în clasa java.util.AbstractCollection
| METODĂ | DESCRIERE |
|---|---|
| conţineAll(Colecţia c) | Returnează true dacă această colecție conține toate elementele din colecția specificată. |
| este gol() | Returnează adevărat dacă această colecție nu conține niciun element. |
| toString() | Returnează o reprezentare șir a acestei colecții. |
Metode declarate în interfața java.util.Collection
| METODĂ | DESCRIERE |
|---|---|
| conţineAll(Colecţia c) | Returnează true dacă această colecție conține toate elementele din colecția specificată. |
| este egal(obiect o) | Compară obiectul specificat cu această colecție pentru egalitate. |
| hashCode() | Returnează valoarea codului hash pentru această colecție. |
| este gol() | Returnează adevărat dacă această colecție nu conține niciun element. |
| parallelStream() | Returnează un flux posibil paralel cu această colecție ca sursă. |
| mărimea() | Returnează numărul de elemente din această colecție. |
| curent() | Returnează un flux secvenţial cu această colecţie ca sursă. |
| toArray (generator de funcții int) | Returnează o matrice care conține toate elementele din această colecție, folosind funcția generator furnizată pentru a aloca matricea returnată. |
Metode declarate în interfața java.util.Queue
| METODĂ | DESCRIERE |
|---|---|
| arunca o privire() | Preia, dar nu elimină, capul acestei cozi sau returnează null dacă această coadă este goală. |
| sondaj() | Preia și elimină capul acestei cozi sau returnează null dacă această coadă este goală. |
Aplicații :
- Implementarea algoritmilor lui Dijkstra și Prim.
- Maximizați suma matricei după K negații
Articole similare :
- Clasa Java.util.PriorityQueue în Java
- Implementați PriorityQueue prin Comparator în Java