Una PriorityQueue viene utilizzata quando si suppone che gli oggetti vengano elaborati in base alla priorità. È noto che l'a Coda segue l'algoritmo First-In-First-Out, ma a volte è necessario che gli elementi della coda siano elaborati in base alla priorità, ecco che entra in gioco PriorityQueue.
PriorityQueue si basa sull'heap delle priorità. Gli elementi della coda con priorità vengono ordinati secondo l'ordinamento naturale, oppure da un comparatore fornito in fase di costruzione della coda, a seconda del costruttore utilizzato.
Nella coda di priorità sottostante, un elemento con un valore ASCII massimo avrà la priorità più alta.
Dichiarazione:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
La classe implementa Serializzabile , Iterabile , Collezione , Coda interfacce.
Alcuni punti importanti sulla coda prioritaria sono come segue:
- PriorityQueue non consente null.
- Non possiamo creare una PriorityQueue di oggetti non comparabili
- PriorityQueue sono code non legate.
- L'inizio di questa coda è l'elemento minimo rispetto all'ordinamento specificato. Se più elementi sono legati per il valore minimo, la testa è uno di quegli elementi: i pareggi vengono risolti arbitrariamente.
- Poiché PriorityQueue non è thread-safe, Java fornisce la classe PriorityBlockingQueue che implementa l'interfaccia BlockingQueue da utilizzare in un ambiente multithreading Java.
- Le operazioni di recupero della coda interrogano, rimuovono, visualizzano e accedono all'elemento in testa alla coda.
- Fornisce tempo O(log(n)) per i metodi di aggiunta e poll.
- Eredita i metodi da AbstractQueue , Collezione astratta , Collezione, E Oggetto classe.
Costruttori:
1. PriorityQueue(): Crea un PriorityQueue con la capacità iniziale predefinita (11) che ordina i suoi elementi in base al loro ordinamento naturale.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (raccolta c): Crea un PriorityQueue contenente gli elementi nella raccolta specificata.
PriorityQueue pq = new PriorityQueue(Collection c);
3. PriorityQueue(int capacitàiniziale) : Crea un PriorityQueue con la capacità iniziale specificata che ordina i suoi elementi in base al loro ordinamento naturale.
PriorityQueue pq = new PriorityQueue(int capacitàiniziale);
4. PriorityQueue(int capacità iniziale, comparatore comparatore): Crea un PriorityQueue con la capacità iniziale specificata che ordina i propri elementi in base al comparatore specificato.
PriorityQueue pq = new PriorityQueue(int partialCapacity, Comparator comparator);
5. PriorityQueue(PriorityQueue c) : Crea una PriorityQueue contenente gli elementi nella coda di priorità specificata.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. Coda di priorità (SortedSet c) : Crea una PriorityQueue contenente gli elementi nel set ordinato specificato.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue (comparatore comparatore): Crea un PriorityQueue con la capacità iniziale predefinita e i cui elementi sono ordinati in base al comparatore specificato.
PriorityQueue pq = new PriorityQueue(Comparatore c);
Esempio:
L'esempio seguente spiega le seguenti operazioni di base della coda di priorità.
gestore attività per linux
- boolean add(E element): questo metodo inserisce l'elemento specificato in questa coda di priorità.
- public peek(): questo metodo recupera, ma non rimuove, l'inizio di questa coda o restituisce null se questa coda è vuota.
- public poll(): questo metodo recupera e rimuove l'inizio di questa coda o restituisce null se questa coda è vuota.
Giava
// 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());> >}> }> |
>
>Produzione
10 10 15>
Operazioni su PriorityQueue
Vediamo come eseguire alcune operazioni utilizzate di frequente sulla classe Priority Queue.
1. Aggiunta di elementi: Per aggiungere un elemento in una coda di priorità, possiamo utilizzare il metodo add(). L'ordine di inserimento non viene mantenuto in PriorityQueue. Gli elementi vengono memorizzati in base all'ordine di priorità che per impostazione predefinita è crescente.
Giava
/*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);> >}> }> |
>
>Produzione
[0, 1, 1, 1, 2, 1]>
Non otterremo elementi ordinati stampando PriorityQueue.
Giava
/*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);> >}> }> |
>
>
come disattivare la modalità sviluppatore su androidProduzione
[For, Geeks, Geeks]>
2. Rimozione di elementi: Per rimuovere un elemento da una coda con priorità, possiamo utilizzare il metodoremove(). Se sono presenti più oggetti di questo tipo, viene rimossa la prima occorrenza dell'oggetto. Oltre a ciò, il metodo poll() viene utilizzato anche per rimuovere la testa e restituirla.
Giava
// 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);> >}> }> |
>
>Produzione
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Accesso agli elementi: Poiché Queue segue il principio First In First Out, possiamo accedere solo al capo della coda. Per accedere agli elementi da una coda con priorità, possiamo utilizzare il metodo peek().
Giava
// 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);> >}> }> |
>
>Produzione
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Iterazione della PriorityQueue: Esistono diversi modi per scorrere PriorityQueue. Il modo più famoso è convertire la coda nell'array e attraversarla utilizzando il ciclo for. Tuttavia, la coda dispone anche di un iteratore integrato che può essere utilizzato per scorrere la coda.
Giava
// 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() +>' '>);> >}> >}> }> |
>
>Produzione
For Geeks Geeks>
Esempio:
Giava
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());> >}> }> |
>
>Produzione
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>
Esempi in tempo reale:
La Priority Queue è una struttura dati in cui gli elementi sono ordinati per priorità, con gli elementi con la priorità più alta che appaiono in testa alla coda. Ecco alcuni esempi reali di dove è possibile utilizzare le code prioritarie:
- Pianificazione delle attività: nei sistemi operativi, le code di priorità vengono utilizzate per pianificare le attività in base ai loro livelli di priorità. Ad esempio, un'attività ad alta priorità come un aggiornamento critico del sistema può essere pianificata prima di un'attività con priorità inferiore come un processo di backup in background. Pronto soccorso: al pronto soccorso dell'ospedale, i pazienti vengono classificati in base alla gravità della loro condizione, con quelli in condizioni critiche che vengono trattati per primi. Una coda prioritaria può essere utilizzata per gestire l'ordine in cui i pazienti vengono visti da medici e infermieri. Routing di rete: nelle reti di computer, le code di priorità vengono utilizzate per gestire il flusso di pacchetti di dati. Ai pacchetti ad alta priorità come i dati vocali e video può essere data priorità rispetto ai dati a priorità più bassa come la posta elettronica e i trasferimenti di file. Trasporti: nei sistemi di gestione del traffico, le code prioritarie possono essere utilizzate per gestire il flusso del traffico. Ad esempio, ai veicoli di emergenza come le ambulanze può essere data la priorità rispetto ad altri veicoli per garantire che possano raggiungere rapidamente la loro destinazione. Pianificazione dei lavori: nei sistemi di pianificazione dei lavori, le code di priorità possono essere utilizzate per gestire l'ordine in cui i lavori vengono eseguiti. I lavori ad alta priorità come gli aggiornamenti critici del sistema possono essere pianificati prima dei lavori a priorità più bassa come i backup dei dati. Mercati online: nei mercati online, le code prioritarie possono essere utilizzate per gestire la consegna dei prodotti ai clienti. Gli ordini ad alta priorità come la spedizione espressa possono avere la priorità rispetto agli ordini di spedizione standard.
Nel complesso, le code di priorità sono una struttura dati utile per gestire attività e risorse in base ai relativi livelli di priorità in vari scenari del mondo reale.
Metodi nella classe PriorityQueue
| METODO | DESCRIZIONE |
|---|---|
| add(E e) | Inserisce l'elemento specificato in questa coda di priorità. |
| chiaro() | Rimuove tutti gli elementi da questa coda di priorità. |
| comparatore() | Restituisce il comparatore utilizzato per ordinare gli elementi in questa coda, o null se questa coda è ordinata secondo l'ordinamento naturale dei suoi elementi. |
| contiene?(Oggetto o) | Restituisce vero se questa coda contiene l'elemento specificato. |
| forEach?(Azione del consumatore) | Esegue l'azione specificata per ciascun elemento dell'Iterable fino a quando tutti gli elementi non sono stati elaborati o l'azione genera un'eccezione. |
| iteratore() | Restituisce un iteratore sugli elementi in questa coda. |
| offerta?(E e) | Inserisce l'elemento specificato in questa coda di priorità. |
| rimuovere?(Oggetto o) | Rimuove una singola istanza dell'elemento specificato da questa coda, se presente. |
| rimuovi tutto?(Raccolta c) | Rimuove tutti gli elementi di questa raccolta contenuti anche nella raccolta specificata (operazione facoltativa). |
| rimuoviSe?(Filtro predicato) | Rimuove tutti gli elementi di questa raccolta che soddisfano il predicato specificato. |
| keepAll?(Raccolta c) | Mantiene solo gli elementi di questa raccolta contenuti nella raccolta specificata (operazione facoltativa). |
| divisore() | Crea uno Spliterator con associazione tardiva e fail-fast sugli elementi in questa coda. |
| toArray() | Restituisce un array contenente tutti gli elementi in questa coda. |
| toArray?(T[] a) | Restituisce un array contenente tutti gli elementi in questa coda; il tipo di runtime dell'array restituito è quello dell'array specificato. |
Metodi dichiarati nella classe java.util.AbstractQueue
| METODO | DESCRIZIONE |
|---|---|
| addAll(Raccolta c) | Aggiunge tutti gli elementi nella raccolta specificata a questa coda. |
| elemento() | Recupera, ma non rimuove, l'inizio di questa coda. |
| rimuovere() | Recupera e rimuove l'inizio di questa coda. |
Metodi dichiarati nella classe java.util.AbstractCollection
| METODO | DESCRIZIONE |
|---|---|
| contieneTutto(Collezione c) | Restituisce vero se questa raccolta contiene tutti gli elementi nella raccolta specificata. |
| è vuoto() | Restituisce vero se questa raccolta non contiene elementi. |
| accordare() | Restituisce una rappresentazione di stringa di questa raccolta. |
Metodi dichiarati nell'interfaccia java.util.Collection
| METODO | DESCRIZIONE |
|---|---|
| contieneTutto(Collezione c) | Restituisce vero se questa raccolta contiene tutti gli elementi nella raccolta specificata. |
| uguale(Oggetto o) | Confronta l'oggetto specificato con questa raccolta per verificarne l'uguaglianza. |
| codice hash() | Restituisce il valore del codice hash per questa raccolta. |
| è vuoto() | Restituisce vero se questa raccolta non contiene elementi. |
| parallelStream() | Restituisce uno Stream possibilmente parallelo con questa raccolta come origine. |
| misurare() | Restituisce il numero di elementi in questa raccolta. |
| flusso() | Restituisce uno stream sequenziale con questa raccolta come origine. |
| toArray(generatore di funzioni Int) | Restituisce un array contenente tutti gli elementi di questa raccolta, utilizzando la funzione generatrice fornita per allocare l'array restituito. |
Metodi dichiarati nell'interfaccia java.util.Queue
| METODO | DESCRIZIONE |
|---|---|
| sbirciare() | Recupera, ma non rimuove, l'inizio di questa coda o restituisce null se questa coda è vuota. |
| sondaggio() | Recupera e rimuove l'inizio di questa coda o restituisce null se questa coda è vuota. |
Applicazioni :
- Implementazione degli algoritmi di Dijkstra e Prim.
- Massimizza la somma dell'array dopo K negazioni
articoli Correlati :
- Classe Java.util.PriorityQueue in Java
- Implementa PriorityQueue tramite Comparator in Java