S'utilitza una PriorityQueue quan se suposa que els objectes s'han de processar en funció de la prioritat. Se sap que a Cua segueix l'algorisme First-In-First-Out, però de vegades cal que els elements de la cua es processin segons la prioritat, és llavors quan entra en joc la PriorityQueue.
PriorityQueue es basa en l'munt de prioritat. Els elements de la cua de prioritat s'ordenen segons l'ordenació natural, o mitjançant un comparador proporcionat en el moment de la construcció de la cua, segons quin constructor s'utilitzi.
A la cua de prioritat següent, un element amb un valor ASCII màxim tindrà la prioritat més alta.
Declaració:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
La classe implementa Serialitzable , Iterable , Col · lecció , Cua interfícies.
Uns quants punts importants a la cua de prioritats són els següents:
- PriorityQueue no permet null.
- No podem crear una cua de prioritats d'objectes que no siguin comparables
- PriorityQueue són cues no vinculades.
- La capçalera d'aquesta cua és l'element menor respecte a l'ordenació especificada. Si hi ha diversos elements lligats pel menor valor, el cap és un d'aquests elements; els enllaços es trenquen arbitràriament.
- Com que PriorityQueue no és segur per a fils, java proporciona la classe PriorityBlockingQueue que implementa la interfície BlockingQueue per utilitzar-la en un entorn de multiprocés de Java.
- Les operacions de recuperació de la cua sondegen, eliminan, miran i accedeixen a l'element al capdavant de la cua.
- Proporciona temps O(log(n)) per als mètodes d'afegit i d'enquesta.
- Hereta mètodes de AbstractQueue , Col·lecció d'abstractes , Col · lecció, i Objecte classe.
Constructors:
1. PriorityQueue(): Crea una PriorityQueue amb la capacitat inicial predeterminada (11) que ordena els seus elements segons el seu ordenament natural.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (Col·lecció c): Crea una PriorityQueue que conté els elements de la col·lecció especificada.
PriorityQueue pq = new PriorityQueue(Col·lecció c);
3. PriorityQueue(int initialCapacity) : Crea una PriorityQueue amb la capacitat inicial especificada que ordena els seus elements segons el seu ordenament natural.
PriorityQueue pq = new PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, comparador comparador): Crea una PriorityQueue amb la capacitat inicial especificada que ordena els seus elements segons el comparador especificat.
PriorityQueue pq = new PriorityQueue(int initialCapacity, comparador comparador);
5. PriorityQueue(PriorityQueue c) : crea una cua de prioritats que conté els elements de la cua de prioritats especificada.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue(SortedSet c) : Crea una PriorityQueue que conté els elements del conjunt ordenat especificat.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue (comparador de comparació): Crea una PriorityQueue amb la capacitat inicial predeterminada i els elements de la qual s'ordenen segons el comparador especificat.
PriorityQueue pq = new PriorityQueue(Comparador c);
Exemple:
L'exemple següent explica les operacions bàsiques següents de la cua de prioritats.
concatenació de cadenes
- boolean add(E element): aquest mètode insereix l'element especificat a aquesta cua de prioritat.
- public peek(): aquest mètode recupera, però no elimina, la capçalera d'aquesta cua, o retorna null si aquesta cua està buida.
- public poll(): aquest mètode recupera i elimina la capçalera d'aquesta cua, o retorna null si aquesta cua està buida.
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());> >}> }> |
>
>Sortida
10 10 15>
Operacions a PriorityQueue
Vegem com realitzar algunes operacions d'ús freqüent a la classe Priority Queue.
1. Afegir elements: Per afegir un element a una cua de prioritat, podem utilitzar el mètode add(). L'ordre d'inserció no es conserva a PriorityQueue. Els elements s'emmagatzemen en funció de l'ordre de prioritat que és ascendent per defecte.
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);> >}> }> |
>
>Sortida
[0, 1, 1, 1, 2, 1]>
No obtindrem elements ordenats imprimint 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);> >}> }> |
>
>
funció anònima javaSortida
[For, Geeks, Geeks]>
2. Eliminació d'elements: Per eliminar un element d'una cua de prioritat, podem utilitzar el mètode remove(). Si hi ha diversos objectes d'aquest tipus, s'elimina la primera ocurrència de l'objecte. A part d'això, també s'utilitza el mètode poll() per treure el cap i tornar-lo.
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);> >}> }> |
>
>Sortida
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Accés als elements: Com que Queue segueix el principi First In First Out, només podem accedir al cap de la cua. Per accedir als elements d'una cua de prioritat, podem utilitzar el mètode 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);> >}> }> |
>
>Sortida
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Iteració de PriorityQueue: Hi ha diverses maneres d'iterar a través de PriorityQueue. La manera més famosa és convertir la cua a la matriu i recórrer mitjançant el bucle for. Tanmateix, la cua també té un iterador integrat que es pot utilitzar per iterar a través de la cua.
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() +>' '>);> >}> >}> }> |
>
>Sortida
For Geeks Geeks>
Exemple:
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());> >}> }> |
>
>Sortida
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>
Exemples en temps real:
La cua de prioritat és una estructura de dades en què els elements s'ordenen per prioritat, amb els elements de prioritat més alta apareixent al capdavant de la cua. Aquests són alguns exemples reals d'on es poden utilitzar les cues de prioritat:
- Programació de tasques: En els sistemes operatius, les cues de prioritat s'utilitzen per programar tasques en funció dels seus nivells de prioritat. Per exemple, una tasca de prioritat alta com una actualització crítica del sistema es pot programar abans d'una tasca de prioritat més baixa com un procés de còpia de seguretat en segon pla. Sala d'urgències: a la sala d'urgències d'un hospital, els pacients són triats en funció de la gravetat de la seva condició, i els que estan en estat crític són tractats primer. Es pot utilitzar una cua de prioritat per gestionar l'ordre en què els metges i les infermeres atenen els pacients. Enrutament de xarxa: a les xarxes d'ordinadors, les cues de prioritat s'utilitzen per gestionar el flux de paquets de dades. Els paquets d'alta prioritat com les dades de veu i de vídeo poden tenir prioritat sobre les dades de prioritat més baixa, com ara el correu electrònic i les transferències de fitxers. Transport: en els sistemes de gestió de trànsit, les cues de prioritat es poden utilitzar per gestionar el flux de trànsit. Per exemple, es pot donar prioritat als vehicles d'emergència com les ambulàncies sobre altres vehicles per garantir que puguin arribar ràpidament al seu destí. Programació de treballs: en els sistemes de planificació de treballs, les cues de prioritat es poden utilitzar per gestionar l'ordre en què s'executen les tasques. Les tasques d'alta prioritat, com ara les actualitzacions crítiques del sistema, es poden programar abans de les tasques de menor prioritat, com ara les còpies de seguretat de dades. Mercats en línia : als mercats en línia, les cues de prioritat es poden utilitzar per gestionar l'entrega de productes als clients. Les comandes d'alta prioritat com l'enviament exprés poden tenir prioritat sobre les comandes d'enviament estàndard.
En general, les cues de prioritat són una estructura de dades útil per gestionar tasques i recursos en funció dels seus nivells de prioritat en diversos escenaris del món real.
Mètodes a la classe PriorityQueue
| MÈTODE | DESCRIPCIÓ |
|---|---|
| afegir (I i) | Insereix l'element especificat a aquesta cua de prioritat. |
| clar () | Elimina tots els elements d'aquesta cua de prioritat. |
| comparador () | Retorna el comparador utilitzat per ordenar els elements d'aquesta cua, o nul si aquesta cua s'ordena segons l'ordenació natural dels seus elements. |
| conté? (Objecte o) | Retorna true si aquesta cua conté l'element especificat. |
| per a cadascú? (acció del consumidor) | Realitza l'acció donada per a cada element de l'iterable fins que s'han processat tots els elements o l'acció genera una excepció. |
| iterador() | Retorna un iterador sobre els elements d'aquesta cua. |
| oferta? (E e) | Insereix l'element especificat a aquesta cua de prioritat. |
| eliminar? (Objecte o) | Elimina una única instància de l'element especificat d'aquesta cua, si està present. |
| removeAll? (Col·lecció c) | Elimina tots els elements d'aquesta col·lecció que també estan continguts a la col·lecció especificada (operació opcional). |
| removeIf? (filtre de predicats) | Elimina tots els elements d'aquesta col·lecció que compleixen el predicat donat. |
| retainAll? (Col·lecció c) | Reté només els elements d'aquesta col·lecció que estan continguts a la col·lecció especificada (operació opcional). |
| divisor () | Crea un Spliterator d'enllaç tardà i d'error ràpid sobre els elements d'aquesta cua. |
| toArray() | Retorna una matriu que conté tots els elements d'aquesta cua. |
| toArray?(T[] a) | Retorna una matriu que conté tots els elements d'aquesta cua; el tipus d'execució de la matriu retornada és el de la matriu especificada. |
Mètodes declarats a la classe java.util.AbstractQueue
| MÈTODE | DESCRIPCIÓ |
|---|---|
| addAll(Col·lecció c) | Afegeix tots els elements de la col·lecció especificada a aquesta cua. |
| element() | Recupera, però no elimina, el cap d'aquesta cua. |
| eliminar () | Recupera i elimina el cap d'aquesta cua. |
Mètodes declarats a la classe java.util.AbstractCollection
| MÈTODE | DESCRIPCIÓ |
|---|---|
| contéAll(Col·lecció c) | Retorna true si aquesta col·lecció conté tots els elements de la col·lecció especificada. |
| està buit() | Retorna true si aquesta col·lecció no conté cap element. |
| toString() | Retorna una representació de cadena d'aquesta col·lecció. |
Mètodes declarats a la interfície java.util.Collection
| MÈTODE | DESCRIPCIÓ |
|---|---|
| contéAll(Col·lecció c) | Retorna true si aquesta col·lecció conté tots els elements de la col·lecció especificada. |
| és igual a (Objecte o) | Compara l'objecte especificat amb aquesta col·lecció per a la igualtat. |
| hashCode() | Retorna el valor del codi hash per a aquesta col·lecció. |
| està buit() | Retorna true si aquesta col·lecció no conté cap element. |
| parallelStream() | Retorna un flux possiblement paral·lel amb aquesta col·lecció com a font. |
| mida () | Retorna el nombre d'elements d'aquesta col·lecció. |
| corrent() | Retorna un flux seqüencial amb aquesta col·lecció com a font. |
| toArray (generador d'IntFunction) | Retorna una matriu que conté tots els elements d'aquesta col·lecció, utilitzant la funció generadora proporcionada per assignar la matriu retornada. |
Mètodes declarats a la interfície java.util.Queue
| MÈTODE | DESCRIPCIÓ |
|---|---|
| ullada() | Recupera, però no elimina, la capçalera d'aquesta cua o retorna null si aquesta cua està buida. |
| enquesta() | Recupera i elimina la capçalera d'aquesta cua o retorna null si aquesta cua està buida. |
Aplicacions :
- Implementació dels algorismes de Dijkstra i Prim.
- Maximitzar la suma de la matriu després de K negacions
Articles relacionats :
- Classe Java.util.PriorityQueue a Java
- Implementar PriorityQueue mitjançant Comparator a Java