Una coda con priorità è un tipo di dati astratto che si comporta in modo simile alla coda normale, tranne per il fatto che ogni elemento ha una certa priorità, ovvero l'elemento con la priorità più alta verrebbe per primo in una coda con priorità. La priorità degli elementi in una coda di priorità determinerà l'ordine in cui gli elementi verranno rimossi dalla coda di priorità.
La coda di priorità supporta solo elementi comparabili, il che significa che gli elementi sono disposti in ordine ascendente o discendente.
for loop java
Ad esempio, supponiamo di avere alcuni valori come 1, 3, 4, 8, 14, 22 inseriti in una coda di priorità con un ordinamento imposto ai valori dal più piccolo al più grande. Pertanto, il numero 1 avrà la priorità più alta mentre 22 avrà la priorità più bassa.
Caratteristiche di una coda prioritaria
Una coda prioritaria è un'estensione di una coda che contiene le seguenti caratteristiche:
- Ad ogni elemento in una coda di priorità è associata una priorità.
- Un elemento con la priorità più alta verrà eliminato prima dell'eliminazione di quello con priorità minore.
- Se due elementi in una coda di priorità hanno la stessa priorità, verranno organizzati utilizzando il principio FIFO.
Comprendiamo la coda con priorità attraverso un esempio.
Abbiamo una coda prioritaria che contiene i seguenti valori:
1, 3, 4, 8, 14, 22
Tutti i valori sono disposti in ordine crescente. Ora osserveremo come apparirà la coda con priorità dopo aver eseguito le seguenti operazioni:
Tipi di coda prioritaria
Esistono due tipi di coda prioritaria:
Rappresentazione della coda prioritaria
Adesso vedremo come rappresentare la coda con priorità tramite una lista unidirezionale.
Creeremo la coda prioritaria utilizzando l'elenco fornito di seguito in cui INFORMAZIONI l'elenco contiene gli elementi di dati, PRN L'elenco contiene i numeri di priorità di ciascun elemento di dati disponibile nel file INFORMAZIONI list e LINK contiene sostanzialmente l'indirizzo del nodo successivo.
Creiamo passo dopo passo la coda prioritaria.
svuotare la cache npm
Nel caso della coda con priorità, il numero di priorità più basso è considerato la priorità più alta, ovvero numero di priorità più basso = priorità più alta.
Passo 1: Nell'elenco, il numero di priorità inferiore è 1, il cui valore dati è 333, quindi verrà inserito nell'elenco come mostrato nel diagramma seguente:
Passo 2: Dopo aver inserito 333, la priorità numero 2 ha una priorità più alta e i valori dei dati associati a questa priorità sono 222 e 111. Pertanto, questi dati verranno inseriti in base al principio FIFO; quindi si aggiungerà prima 222 e poi 111.
Passaggio 3: Dopo aver inserito gli elementi con priorità 2, il numero di priorità immediatamente superiore è 4 e gli elementi di dati associati a 4 numeri di priorità sono 444, 555, 777. In questo caso, gli elementi verrebbero inseriti in base al principio FIFO; pertanto verrà aggiunto prima 444, poi 555 e infine 777.
Passaggio 4: Dopo aver inserito gli elementi con priorità 4, il numero di priorità immediatamente superiore è 5 e il valore associato alla priorità 5 è 666, quindi verrà inserito alla fine della coda.
Implementazione della coda prioritaria
La coda di priorità può essere implementata in quattro modi che includono array, elenco collegato, struttura dei dati heap e albero di ricerca binaria. La struttura dei dati heap è il modo più efficiente per implementare la coda di priorità, quindi in questo argomento implementeremo la coda di priorità utilizzando una struttura di dati heap. Ora, per prima cosa capiamo il motivo per cui l'heap è il modo più efficiente tra tutte le altre strutture dati.
Analisi delle complessità utilizzando diverse implementazioni
| Implementazione | aggiungere | Rimuovere | sbirciare |
| Lista collegata | O(1) | SU) | SU) |
| Mucchio binario | O(log) | O(log) | O(1) |
| Albero di ricerca binario | O(log) | O(log) | O(1) |
Cos'è l'heap?
Un heap è una struttura dati basata su albero che forma un albero binario completo e soddisfa la proprietà dell'heap. Se A è un nodo genitore di B, allora A è ordinato rispetto al nodo B per tutti i nodi A e B in un heap. Ciò significa che il valore del nodo genitore potrebbe essere maggiore o uguale al valore del nodo figlio, oppure il valore del nodo genitore potrebbe essere inferiore o uguale al valore del nodo figlio. Pertanto possiamo dire che esistono due tipi di heap:
Entrambi gli heap sono heap binari, poiché ciascuno ha esattamente due nodi figli.
Operazioni sulla coda prioritaria
Le operazioni comuni che possiamo eseguire su una coda prioritaria sono inserimento, cancellazione e peek. Vediamo come possiamo mantenere la struttura dei dati dell'heap.
Se inseriamo un elemento in una coda con priorità, si sposterà nello slot vuoto guardando dall'alto verso il basso e da sinistra a destra.
Se l'elemento non è nella posizione corretta allora viene confrontato con il nodo genitore; se viene trovato fuori ordine, gli elementi vengono scambiati. Questo processo continua finché l'elemento non viene posizionato nella posizione corretta.
Come sappiamo, in un heap massimo, l'elemento massimo è il nodo radice. Quando rimuoviamo il nodo radice, crea uno slot vuoto. L'ultimo elemento inserito verrà aggiunto in questo slot vuoto. Quindi, questo elemento viene confrontato con i nodi figli, ovvero il figlio sinistro e il figlio destro, e scambiato con il più piccolo dei due. Continua a spostarsi lungo l'albero finché la proprietà dell'heap non viene ripristinata.
Applicazioni della coda prioritaria
Di seguito sono riportate le applicazioni della coda di priorità:
sottolineare nel ribasso
- Viene utilizzato nell'algoritmo del percorso più breve di Dijkstra.
- È utilizzato nell'algoritmo di Prim
- Viene utilizzato nelle tecniche di compressione dei dati come il codice Huffman.
- Viene utilizzato nell'ordinamento heap.
- Viene utilizzato anche nel sistema operativo come pianificazione delle priorità, bilanciamento del carico e gestione degli interrupt.
Programma per creare la coda con priorità utilizzando l'heap massimo binario.
#include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i > 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong> </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>