CUA DE PRIORITATS (ESTRUCTURES DE DADES)

Una cua de prioritat és un tipus de dades abstracte que es comporta de manera semblant a la cua normal, excepte que cada element té alguna prioritat, és a dir, l'element amb la prioritat més alta passaria primer en una cua de prioritat. La prioritat dels elements d'una cua de prioritats determinarà l'ordre en què s'eliminen els elements de la cua de prioritats.

La cua de prioritat només admet elements comparables, el que significa que els elements estan disposats en ordre ascendent o descendent.

què és el maneig d'excepcions a Java

Per exemple, suposem que tenim alguns valors com 1, 3, 4, 8, 14, 22 inserits en una cua de prioritats amb un ordre imposat als valors de menor a major. Per tant, el número 1 tindria la prioritat més alta, mentre que el 22 tindria la prioritat més baixa.

Característiques d'una cua de prioritat

Una cua de prioritat és una extensió d'una cua que conté les característiques següents:

Cada element d'una cua de prioritats té associada alguna prioritat.
Un element amb la prioritat més alta s'eliminarà abans de la supressió de la prioritat menor.
Si dos elements d'una cua de prioritat tenen la mateixa prioritat, s'organitzaran mitjançant el principi FIFO.

Entenem la cua de prioritats a través d'un exemple.

Tenim una cua de prioritats que conté els valors següents:

1, 3, 4, 8, 14, 22

Tots els valors estan ordenats en ordre ascendent. Ara, veurem com quedarà la cua de prioritats després de realitzar les operacions següents:

enquesta():Aquesta funció eliminarà l'element de prioritat més alta de la cua de prioritat. A la cua de prioritat anterior, l'element '1' té la prioritat més alta, de manera que s'eliminarà de la cua de prioritat.afegir (2):Aquesta funció inserirà l'element '2' en una cua de prioritat. Com que 2 és l'element més petit entre tots els nombres, obtindrà la prioritat més alta.enquesta():Eliminarà l'element '2' de la cua de prioritats, ja que té la cua de prioritat més alta.afegir (5):Insereix 5 elements després de 4, ja que 5 és més gran que 4 i menor que 8, de manera que obtindrà la tercera prioritat més alta en una cua de prioritats.

Tipus de cua de prioritat

Hi ha dos tipus de cues de prioritat:

Representació de la cua de prioritat

Ara, veurem com representar la cua de prioritats mitjançant una llista unidireccional.

Crearem la cua de prioritats utilitzant la llista que es mostra a continuació en què INFO llista conté els elements de dades, PRN llista conté els números de prioritat de cada element de dades disponible al INFO llista, i LINK bàsicament conté l'adreça del següent node.

Creem la cua de prioritats pas a pas.

tostring java

En el cas de la cua de prioritat, el número de prioritat més baixa es considera la prioritat més alta, és a dir, número de prioritat més baixa = prioritat més alta.

Pas 1: A la llista, el número de prioritat més baixa és 1, el valor de les dades és 333, de manera que s'inserirà a la llista tal com es mostra al diagrama següent:

Pas 2: Després d'inserir 333, la prioritat número 2 té una prioritat més alta, i els valors de dades associats amb aquesta prioritat són 222 i 111. Per tant, aquestes dades s'inseriran segons el principi FIFO; per tant, primer s'afegiran 222 i després 111.

Pas 3: Després d'inserir els elements de prioritat 2, el número de prioritat següent més alt és 4 i els elements de dades associats a 4 números de prioritat són 444, 555, 777. En aquest cas, els elements s'inseririen segons el principi FIFO; per tant, primer s'afegiran 444, després 555 i després 777.

Pas 4: Després d'inserir els elements de la prioritat 4, el número de prioritat següent més alt és 5 i el valor associat a la prioritat 5 és 666, de manera que s'inserirà al final de la cua.

Implementació de la cua de prioritats

La cua de prioritats es pot implementar de quatre maneres que inclouen matrius, llista enllaçada, estructura de dades de pila i arbre de cerca binari. L'estructura de dades d'emmagatzematge dinàmic és la forma més eficient d'implementar la cua de prioritats, de manera que implementarem la cua de prioritat mitjançant una estructura de dades d'emmagatzematge en aquest tema. Ara, primer entenem la raó per la qual la pila és la forma més eficient entre totes les altres estructures de dades.

Anàlisi de complexitats mitjançant diferents implementacions

Implementació	afegir	Eliminar	ullada
Llista enllaçada	O(1)	O(n)	O(n)
Munt binari	O (inici de sessió)	O (inici de sessió)	O(1)
Arbre de cerca binari	O (inici de sessió)	O (inici de sessió)	O(1)

Què és Heap?

Un munt és una estructura de dades basada en un arbre que forma un arbre binari complet i satisfà la propietat del munt. Si A és un node pare de B, llavors A s'ordena respecte al node B per a tots els nodes A i B en un munt. Vol dir que el valor del node pare podria ser més o igual que el valor del node fill, o el valor del node pare podria ser inferior o igual al valor del node fill. Per tant, podem dir que hi ha dos tipus de munts:

què és desktop ini

Tots dos munts són el munt binari, ja que cadascun té exactament dos nodes fills.

Operacions de cua prioritàries

Les operacions habituals que podem realitzar en una cua de prioritat són la inserció, la supressió i la visualització. Vegem com podem mantenir l'estructura de dades de l'heap.

Inserció de l'element en una cua de prioritat (munt màxim)

Si inserim un element en una cua de prioritat, es mourà a la ranura buida mirant de dalt a baix i d'esquerra a dreta.

Si l'element no es troba al lloc correcte, es compara amb el node pare; si es troba fora d'ordre, els elements s'intercanvien. Aquest procés continua fins que l'element es col·loca en una posició correcta.

Eliminació de l'element mínim de la cua de prioritats

Com sabem que en un munt màxim, l'element màxim és el node arrel. Quan eliminem el node arrel, es crea una ranura buida. L'últim element inserit s'afegirà a aquesta ranura buida. Aleshores, aquest element es compara amb els nodes fill, és a dir, el fill esquerre i el fill dret, i s'intercanvia amb el més petit dels dos. Continua movent-se per l'arbre fins que es restaura la propietat del munt.

Aplicacions de la cua de prioritats

A continuació es mostren les aplicacions de la cua de prioritats:

S'utilitza en l'algorisme del camí més curt de Dijkstra.
S'utilitza en l'algorisme de prim
S'utilitza en tècniques de compressió de dades com el codi Huffman.
S'utilitza en l'ordenació de pila.
També s'utilitza en sistemes operatius com la programació de prioritats, l'equilibri de càrrega i el maneig d'interrupcions.

Programa per crear la cua de prioritats utilitzant el munt màxim binari.

 #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 &gt; 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])>

TechCodeview

Què és una cua de prioritat?