Coda prioritaria nella struttura dei dati: caratteristiche, tipi e implementazione

Pubblicato: 2021-05-02

Sommario

introduzione

La coda di priorità nella struttura dati è un'estensione della coda "normale". È un tipo di dati astratto che contiene un gruppo di elementi. È come la coda "normale", tranne per il fatto che gli elementi di rimozione dalla coda seguono un ordine di priorità. L'ordine di priorità rimuove prima dalla coda gli elementi che hanno la priorità più alta. Questo blog ti fornirà una comprensione più approfondita della coda di priorità e della sua implementazione nel linguaggio di programmazione C.

Che cos'è una coda prioritaria?

È un tipo di dati astratto che fornisce un modo per mantenere il set di dati. La coda "normale" segue uno schema di first-in-first-out. Elimina gli elementi dalla coda nello stesso ordine seguito al momento dell'operazione di inserimento. Tuttavia, l'ordine degli elementi in una coda di priorità dipende dalla priorità dell'elemento in quella coda. La coda di priorità sposta gli elementi di priorità più alta all'inizio della coda di priorità e gli elementi di priorità più bassa in fondo alla coda di priorità.

Supporta solo quegli elementi che sono comparabili. Quindi, una coda di priorità nella struttura dati dispone gli elementi in ordine crescente o decrescente.

Puoi pensare a una coda prioritaria come a diversi pazienti che aspettano in fila in un ospedale. Qui, la situazione del paziente definisce l'ordine di priorità. Il paziente con la lesione più grave sarebbe il primo della coda.

Quali sono le caratteristiche di una coda prioritaria?

Una coda viene definita coda prioritaria se presenta le seguenti caratteristiche:

  • Ogni elemento ha una priorità ad esso associata.
  • Un elemento con la priorità più alta viene spostato in primo piano ed eliminato per primo.
  • Se due elementi condividono lo stesso valore di priorità, la coda di priorità segue il principio first-in-first-out per l'operazione di rimozione della coda.

Quali sono i tipi di coda prioritaria?

Una coda prioritaria è di due tipi:

  • Coda di priorità ordine crescente
  • Coda di priorità ordine decrescente

Coda di priorità ordine crescente

Una coda con priorità di ordine crescente assegna la priorità più alta al numero inferiore in quella coda. Ad esempio, hai sei numeri nella coda di priorità che sono 4, 8, 12, 45, 35, 20. Innanzitutto, disporrai questi numeri in ordine crescente. Il nuovo elenco è il seguente: 4, 8, 12, 20. 35, 45. In questo elenco, 4 è il numero più piccolo. Pertanto, la coda di priorità dell'ordine crescente considera il numero 4 come la priorità più alta.

4 8 12 20 35 45

Nella tabella sopra, 4 ha la priorità più alta e 45 ha la priorità più bassa.

Coda di priorità ordine decrescente

Una coda con priorità di ordine decrescente assegna la priorità più alta al numero più alto in quella coda. Ad esempio, hai sei numeri nella coda di priorità che sono 4, 8, 12, 45, 35, 20. Innanzitutto, disporrai questi numeri in ordine crescente. Il nuovo elenco è il seguente: 45, 35, 20, 12, 8, 4. In questo elenco, 45 è il numero più alto. Pertanto, la coda di priorità dell'ordine decrescente considera il numero 45 come la priorità più alta.

45 35 20 12 8 4

Nella tabella sopra, 4 ha la priorità più bassa e 45 ha la priorità più alta.

Implementazione della coda prioritaria nella struttura dei dati

È possibile implementare le code prioritarie in uno dei seguenti modi:

  • Lista collegata
  • Heap binario
  • Matrici
  • Albero di ricerca binario

L'heap binario è il metodo più efficiente per implementare la coda di priorità nella struttura dei dati .

Le tabelle seguenti riepilogano la complessità delle diverse operazioni in una coda prioritaria.

Operazione Matrice non ordinata Matrice ordinata Heap binario Albero di ricerca binaria
Inserire 0(1) 0(N) 0(log(N)) 0(log(N))
Sbirciare 0(N) 0(1) 0(1) 0(1)
Eliminare 0(N) 0(1) 0(log (N)) 0(log(N))

Heap binario

Un albero di heap binario organizza tutti i nodi padre e figlio dell'albero in un ordine particolare. In un albero di heap binario, un nodo padre può avere un massimo di 2 nodi figlio. Il valore del nodo padre può essere:

  • uguale o inferiore al valore di un nodo figlio.
  • uguale o superiore al valore di un nodo figlio.

Il processo precedente divide l'heap binario in due tipi: max heap e min-heap.

Massimo Mucchio

L'heap massimo è un heap binario in cui un nodo padre ha un valore uguale o maggiore del valore del nodo figlio. Il nodo radice dell'albero ha il valore più alto.

Inserimento di un elemento in un albero binario di Max Heap

È possibile eseguire i seguenti passaggi per inserire un elemento/numero nella coda di priorità nella struttura dati .

  1. L'algoritmo esegue la scansione dell'albero dall'alto verso il basso e da sinistra a destra per trovare uno slot vuoto. Quindi inserisce l'elemento nell'ultimo nodo dell'albero.
  2. Dopo aver inserito l'elemento, l'ordine dell'albero binario è disturbato. È necessario scambiare i dati tra loro per ordinare l'ordine dell'albero binario dell'heap massimo. È necessario continuare a mescolare i dati finché l'albero non soddisfa la proprietà max-heap.

Algoritmo per inserire un elemento in un albero binario di Max Heap

Se l'albero è vuoto e non contiene alcun nodo,

crea un nuovo nodo padre newElement.

else (un nodo padre è già disponibile)

inserire il newElement alla fine dell'albero (cioè l'ultimo nodo dell'albero da sinistra a destra.)

max-heapify l'albero

Eliminazione di un elemento in un albero binario di Max Heap

  1. È possibile eseguire i passaggi seguenti per eliminare un elemento nella coda di priorità in Struttura dati .
  2. Scegli l'elemento che desideri eliminare dall'albero binario.
  3. Sposta i dati alla fine dell'albero scambiandoli con i dati dell'ultimo nodo.
  4. Rimuovere l'ultimo elemento dell'albero binario.
  5. Dopo aver eliminato l'elemento, l'ordine dell'albero binario è disturbato. È necessario ordinare l'ordine per soddisfare la proprietà di max-heap. Devi continuare a mescolare i dati finché l'albero non incontra la proprietà max-heap.

Algoritmo per eliminare un elemento in un albero binario di Max Heap

Se elementUpForDeletion è l'ultimoNode,

eliminare l'elementoUpForDeletion

altrimenti sostituisci elementUpForDeletion con lastNode

eliminare l'elementoUpForDeletion

max-heapify l'albero

Trova l'elemento massimo o minimo in un albero binario di heap massimo

In un albero binario max heap, l'operazione di ricerca restituisce il nodo padre (l'elemento più alto) dell'albero.

Algoritmo per trovare il massimo o il minimo in un albero binario di heap massimo

restituisce ParentNode

Implementazione del programma della Priority Queue utilizzando il Max Heap Binary Tree

#include <stdio.h>

int albero_binario = 10;

int max_heap = 0;

const int test = 100000;

void swap( int *x, int *y ) {

int a;

a = *x;

*x= *y;

*y = a;

}

//Codice per trovare il genitore nell'albero dell'heap massimo

int findParentNode(int node[], int root) {

if ((radice > 1) && (radice < albero_binario)) {

restituisce radice/2;

}

ritorno -1;

}

void max_heapify(int node[], int root) {

int leftNodeRoot = trovaLeftChild(nodo, radice);

int rightNodeRoot = trovaRightChild(nodo, radice);

// trova il più alto tra root, figlio sinistro e figlio destro

int più alto = radice;

if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

if (node[leftNodeRoot] > nodo[più alto]) {

più alto = leftNodeRoot;

}

}

if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

if (node[rightNodeRoot] > nodo[più alto]) {

più alto = rightNodeRoot;

}

}

if (il più alto != radice) {

swap(&node[root], &node[più alto]);

max_heapify(nodo, più alto);

}

}

void create_max_heap(int node[]) {

int d;

for(d=max_heap/2; d>=1; d–) {

max_heapify(nodo, d);

}

}

int massimo(int nodo[]) {

nodo di ritorno[1];

}

int find_max(int ​​node[]) {

int maxNode = nodo[1];

nodo[1] = nodo[max_heap];

max_heap–;

max_heapify(nodo, 1);

restituisce maxNode;

}

void defend_key(int node[], int node, int key) {

A[radice] = chiave;

max_heapify(nodo, radice);

}

void aumento_key(int node[], int root, int key) {

nodo[radice] = chiave;

while((root>1) && (node[findParentNode(node, root)] < node[root])) {

swap(&node[root], &node[findParentNode(node, root)]);

radice = trovaNodoParent(nodo, radice);

}

}

void insert(int node[], int key) {

max_heap++;

nodo[max_heap] = -1*test;

aumento_chiave(nodo, max_heap, chiave);

}

void display_heap(int node[]) {

int d;

for(d=1; d<=max_heap; d++) {

printf(“%d\n”,node[d]);

}

printf(“\n”);

}

int principale() {

nodo int[albero_binario];

inserisci(nodo, 10);

inserisci(nodo, 4);

inserisci(nodo, 20);

inserisci(nodo, 50);

inserisci(nodo, 1);

inserisci(nodo, 15);

display_heap(nodo);

printf(“%d\n\n”, massimo(nodo));

display_heap(nodo);

printf(“%d\n”, extract_max(nodo));

printf(“%d\n”, extract_max(nodo));

restituire 0;

}

Min Heap

Il min-heap è un heap binario in cui un nodo padre ha un valore uguale o inferiore al valore del nodo figlio. Il nodo radice dell'albero ha il valore più basso.

È possibile implementare il min-heap nello stesso modo del max-heap, tranne che invertire l'ordine.

Conclusione

Gli esempi forniti nell'articolo sono solo a scopo esplicativo. È possibile modificare le dichiarazioni sopra riportate in base alle proprie esigenze. In questo blog abbiamo appreso il concetto di coda di priorità nella struttura dei dati . Puoi provare l'esempio per rafforzare la tua conoscenza della struttura dei dati.

Se sei curioso di conoscere la scienza dei dati, dai un'occhiata al programma Executive PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1 -on-1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.

Impara i corsi di scienza dei dati online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.

Quali sono le applicazioni di una coda prioritaria?

La coda di priorità è una coda speciale in cui gli elementi vengono inseriti in base alla loro priorità. Questa funzione si rivela utile nell'implementazione di varie altre strutture di dati. Di seguito sono elencate alcune delle applicazioni più popolari della coda di priorità:
 1. Algoritmo del percorso più breve di Dijkstra: la coda di priorità può essere utilizzata nell'algoritmo del percorso più breve di Dijkstra quando il grafico è archiviato sotto forma di elenco di adiacenza.
 2. Algoritmo di Prim: l'algoritmo di Prim utilizza la coda di priorità per i valori o le chiavi dei nodi e estrae il minimo di questi valori ad ogni passaggio.
 Compressione dei dati : i codici Huffman utilizzano la coda di priorità per comprimere i dati.
 Sistemi operativi: la coda di priorità è molto utile per i sistemi operativi in ​​vari processi come il bilanciamento del carico e la gestione delle interruzioni.

Quale approccio viene utilizzato nell'implementazione della coda di priorità utilizzando l'array?

L'approccio utilizzato nell'implementazione della coda di priorità utilizzando un array è semplice. Viene creata una struttura per memorizzare i valori e la priorità dell'elemento e quindi viene creato l'array di tale struttura per memorizzare gli elementi. In questa implementazione sono coinvolte le seguenti operazioni:
 1. enqueue()-Questa funzione inserisce gli elementi alla fine della coda.
 2. peek() - Questa funzione attraverserà l'array per restituire l'elemento con la priorità più alta. Se trova due elementi con la stessa priorità, restituisce l'elemento di valore più alto tra di loro.
 3. dequeue() - Questa funzione sposterà tutti gli elementi, 1 posizione a sinistra dell'elemento restituito dalla funzione peek() e ridurrà le dimensioni.

Qual è la differenza tra max heap e min heap?

Di seguito viene illustrata la differenza tra max heap e min-heap.
 Min Heap - In un min-heap, la chiave del nodo radice deve essere minore o uguale alle chiavi del relativo nodo figlio. Utilizza la priorità crescente. Il nodo con la chiave più piccola è la priorità. L'elemento più piccolo viene visualizzato prima di qualsiasi altro elemento.
 Max Heap - In un max heap, la chiave del nodo radice deve essere maggiore o uguale alla chiave dei suoi nodi figli. Utilizza la priorità discendente. Il nodo con la chiave più grande è la priorità. L'elemento più grande viene visualizzato prima di qualsiasi altro elemento.