priority queue data structure c with illustration
Introduzione alla coda prioritaria in C ++ con illustrazione.
Priority Queue è un'estensione della coda di cui abbiamo discusso nel nostro ultimo tutorial.
È simile alla coda per certi aspetti e tuttavia differisce dalla coda ordinaria per i seguenti punti:
- Ogni elemento nella coda di priorità è associato a una priorità.
- L'elemento con la priorità più alta è il primo elemento a essere rimosso dalla coda.
- Se più di un elemento ha la stessa priorità, viene preso in considerazione il loro ordine nella coda.
=> Fare clic qui per la serie di formazione Absolute C ++.
Possiamo visualizzare la coda con priorità come una versione modificata della coda, tranne per il fatto che quando l'elemento deve essere rimosso dalla coda, l'elemento con la priorità più alta viene recuperato per primo. Quindi preferiamo utilizzare le code di priorità invece delle code quando dobbiamo elaborare gli elementi in base alla priorità.
Cosa imparerai:
- Operazioni di base
- Illustrazione
- Implementazione di code prioritarie in C ++
- Applicazione
- Conclusione
- Lettura consigliata
Operazioni di base
Parliamo di alcune delle operazioni di base supportate dalla coda di priorità.
- Inserisci (elemento, priorità): Inserisce un elemento nella coda di priorità con una data priorità.
- getHighestPriority (): Restituisce un articolo con la massima priorità.
- deleteHighestPriority (): Rimuove un elemento con la massima priorità.
Oltre alle operazioni precedenti, possiamo anche usare le normali operazioni di coda come isEmpty (), isFull () e peek ().
Illustrazione
Vediamo un'illustrazione della coda di priorità. Per semplicità, useremo caratteri ASCII come elementi nella coda di priorità. Maggiore è il valore ASCII, maggiore è la priorità.
Stato iniziale - Priority Queue (PQ) - {} => vuoto
Dall'illustrazione sopra, vediamo che l'operazione di inserimento è simile a una coda ordinaria. Ma quando chiamiamo 'deleteHighestPriority' per la coda di priorità, l'elemento con la priorità più alta viene rimosso per primo.
Quindi la prima volta che chiamiamo questa funzione, l'elemento O viene rimosso mentre la seconda volta, l'elemento M viene rimosso poiché ha una priorità maggiore di G e A.
Implementazione di code prioritarie in C ++
Le code prioritarie possono essere implementate utilizzando:
# 1) Array / elenchi collegati
Possiamo implementare le code con priorità utilizzando gli array e questa è l'implementazione più semplice per le code con priorità.
Per rappresentare gli elementi nella coda di priorità, possiamo semplicemente dichiarare una struttura come di seguito:
struct pq_item{ int item; int priority; };
Abbiamo dichiarato anche la priorità per ogni articolo.
Per inserire un nuovo elemento nella coda delle priorità dobbiamo semplicemente inserire l'elemento alla fine dell'array.
Per ottenere l'elemento dalla coda utilizzando getHighestPriority (), è necessario attraversare l'array dall'inizio e restituire l'elemento con la priorità più alta.
Allo stesso modo, per rimuovere l'elemento dalla coda utilizzando l'operazione deleteHighestPriority, è necessario attraversare l'intero array ed eliminare l'elemento con la priorità più alta. Quindi sposta tutti gli altri elementi dopo l'elemento eliminato di una posizione indietro.
Possiamo anche implementare la coda di priorità utilizzando un elenco collegato. Possiamo eseguire tutte le operazioni in modo simile come gli array. L'unica differenza è che non è necessario spostare gli elementi dopo aver chiamato deleteHighestPriority.
# 2) Mucchi
L'utilizzo di heap per implementare una coda di priorità è il modo più efficiente e fornisce prestazioni molto migliori rispetto agli elenchi e agli array collegati. Contrariamente all'elenco e all'array collegati, l'implementazione dell'heap richiede tempo O (logn) per le operazioni di inserimento ed eliminazione della coda prioritaria. Ottieni operazione, getHighestPriority richiede O (1) tempo.
# 3) Coda di priorità incorporata nella libreria di modelli standard (STL) in C ++
In C ++, abbiamo una coda prioritaria come classe adattiva del contenitore, progettata in modo tale che l'elemento più alto sia il primo elemento della coda e tutti gli elementi siano in ordine decrescente.
Pertanto ogni elemento nella coda di priorità ha una priorità fissa.
Abbiamo una classe in STL, che contiene l'implementazione della coda di priorità.
Le varie operazioni supportate dalla coda di priorità sono le seguenti:
- priority_queue :: size (): Restituisce la dimensione della coda.
- priority_queue :: empty (): Controlla se la coda è vuota e restituisce il suo stato.
- priority_queue :: top (): Restituisce un riferimento all'elemento più in alto della coda di priorità.
- priority_queue :: push (): Aggiunge un elemento alla fine della coda di priorità.
- priority_queue :: pop (): Rimuove il primo elemento dalla coda di priorità.
- priority_queue :: swap (): Utilizzato per scambiare il contenuto di una coda di priorità con un'altra dello stesso tipo e dimensione.
- tipo di valore della coda di priorità: Il tipo di valore fornisce il tipo di elemento memorizzato in una coda di priorità. Questo funge anche da sinonimo per il parametro template.
- priority_queue :: emplace (): Utilizzato per inserire un nuovo elemento nel contenitore della coda di priorità nella parte superiore della coda.
Nel prossimo programma vedremo la funzionalità della coda di priorità in STL in C ++.
#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << '
'; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << '
Top element of the queue(pq.top()): ' << pq.top(); cout << '
The priority queue pq is : '; displaypq(pq); cout << '
Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; }
Produzione:
compilatore c ++ per eclipse
Dimensione della coda (pq.size ()): 5
Elemento in cima alla coda (pq.top ()): 9
La coda di priorità pq è: 9 7 5 3 1
Coda prioritaria, dopo l'operazione pq.pop (): 7 5 3 1
Implementazione Java per coda prioritaria
La coda prioritaria in java è una coda speciale in cui tutti gli elementi nella coda vengono ordinati in base all'ordinamento naturale o personalizzato utilizzando un comparatore fornito con la coda.
Una coda prioritaria in Java ha l'aspetto mostrato di seguito:
Nella coda di priorità Java, gli elementi sono disposti in modo tale che l'elemento minimo si trovi nella parte anteriore della coda e l'elemento più grande sia nella parte posteriore della coda. Quindi, quando rimuoviamo l'elemento dalla coda di priorità, è sempre l'elemento più piccolo che viene rimosso.
La classe che implementa la coda di priorità in Java è 'PriorityQueue' e fa parte del framework delle collezioni di Java. Implementa l'interfaccia 'Queue' di Java.
Di seguito è riportata la gerarchia delle classi per la classe Java PriorityQueue.
Di seguito è riportato un esempio di funzionalità di coda prioritaria con numeri interi come elementi in Java.
import java.util.*; class Main { public static void main(String args[]) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println('
After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println('
After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( '
Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object[] arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i Produzione:
peek () :: Valore della testa: 1
La coda delle priorità:
1 3 5 7
Dopo la funzione poll (), coda di priorità:
3 7 5
Dopo la funzione Rimuovi (5), coda di priorità:
3 7
La coda prioritaria contiene 3 ?: true
Elementi della matrice:
Valore: 3
Valore: 7
Nel programma precedente, utilizziamo la classe PriorityQueue di Java per creare un oggetto di PriorityQueue che contiene un oggetto Integer. Aggiungiamo elementi alla coda utilizzando la funzione 'aggiungi'. Quindi viene chiamata la funzione poll () che cancella l'elemento dalla parte anteriore della coda che risulta essere l'elemento minimo.
Ancora una volta chiamiamo la funzione 'remove ()' che rimuove l'elemento specificato come parametro dalla coda. Usiamo anche la funzione “Contains ()” per controllare se un particolare elemento è presente nella coda. Infine, convertiamo la coda in un oggetto array utilizzando la funzione 'toArray ()'.
Applicazione
- Bilanciamento del carico del sistema operativo e gestori di interrupt: Le funzioni del sistema operativo come il bilanciamento del carico e la gestione degli interrupt sono implementate utilizzando code di priorità. L'attività di bilanciamento del carico pianifica le risorse con la massima priorità al fine di sostenere efficacemente il nostro bilanciamento del carico. La gestione degli interrupt viene eseguita servendo gli interrupt con la massima priorità. Questa funzionalità può essere efficacemente implementata utilizzando le code di priorità.
- Routing: Il routing è una funzione che viene utilizzata per instradare le risorse di rete in modo da ottenere il massimo throughput con tempi di consegna minimi. Ciò può essere implementato anche utilizzando la coda di priorità.
- Emergenza ospedaliera: In un pronto soccorso ospedaliero, i pazienti vengono assistiti in base alla gravità delle condizioni del paziente. Questo può essere simulato utilizzando le code di priorità.
- Algoritmo del percorso più breve di Dijkstra: Qui il grafico è memorizzato come un elenco di adiacenza e possiamo usare una coda di priorità per estrarre il bordo minimo pesato in modo efficiente dall'elenco di adiacenza per implementare l'algoritmo del percorso più breve di Dijkstra.
- La coda prioritaria può anche essere utilizzata per memorizzare le chiavi del nodo ed estrarre il nodo chiave minimo durante l'implementazione dell'albero di copertura.
Conclusione
Le code prioritarie non sono altro che l'estensione della coda. Ma a differenza delle code che aggiungono / rimuovono elementi utilizzando l'approccio FIFO, nella coda di priorità gli elementi vengono rimossi dalla coda in base alla priorità. Pertanto, ogni elemento nella coda è associato a una priorità e l'elemento con la priorità più alta è il primo ad essere rimosso dalla coda.
La coda di priorità ha tre operazioni principali, ovvero insert (), getHighestPriority () e deleteHighestPriority (). La coda prioritaria può essere implementata utilizzando array o elenchi collegati ma il funzionamento non è molto efficiente. La coda prioritaria può anche essere implementata utilizzando gli heap e le prestazioni sono molto più veloci.
In C ++, abbiamo anche una classe contenitore che implementa la funzionalità di una coda di priorità. In Java, è presente una classe priority_queue incorporata che fornisce la funzionalità di una coda di priorità.
La coda di priorità viene utilizzata principalmente nelle applicazioni che richiedono l'elaborazione degli elementi in base alla priorità. Per esempio, viene utilizzato nella gestione degli interrupt.
Il nostro prossimo tutorial esplorerà tutto sulla coda circolare che è ancora un'altra estensione della coda.
=> Visita qui per il corso completo C ++ degli esperti.
Lettura consigliata
- Struttura dei dati della coda in C ++ con illustrazione
- Coda prioritaria in AWL
- Stack Struttura Dati In C ++ Con Illustrazione
- Struttura Dati Elenco Collegato Circolare In C ++ Con Illustrazione
- Struttura Dati Elenco Collegato In C ++ Con Illustrazione
- Struttura dei dati della lista doppiamente collegata in C ++ con illustrazione
- Introduzione alle strutture dati in C ++
- Come testare la coda di messaggistica dell'applicazione: IBM WebSphere MQ Intro Tutorial