O coadă cu prioritate este un tip de date abstracte care se comportă similar cu o coadă normală, cu excepția faptului că fiecare element are o anumită prioritate, adică elementul cu cea mai mare prioritate ar fi primul într-o coadă de prioritate. Prioritatea elementelor dintr-o coadă de prioritate va determina ordinea în care elementele sunt eliminate din coada de prioritate.
Coada de prioritate acceptă numai elemente comparabile, ceea ce înseamnă că elementele sunt fie aranjate în ordine crescătoare, fie în ordine descrescătoare.
df loc
De exemplu, să presupunem că avem niște valori precum 1, 3, 4, 8, 14, 22 introduse într-o coadă de prioritate cu o ordonare impusă valorilor de la cel mai mic la cel mai mare. Prin urmare, numărul 1 va avea cea mai mare prioritate, în timp ce 22 va avea cea mai mică prioritate.
Caracteristicile unei cozi de prioritate
O coadă prioritară este o extensie a unei cozi care conține următoarele caracteristici:
- Fiecare element dintr-o coadă de prioritate are o anumită prioritate asociată cu el.
- Un element cu prioritate mai mare va fi șters înainte de ștergerea priorității mai mici.
- Dacă două elemente dintr-o coadă de prioritate au aceeași prioritate, acestea vor fi aranjate folosind principiul FIFO.
Să înțelegem coada de priorități printr-un exemplu.
Avem o coadă de prioritate care conține următoarele valori:
1, 3, 4, 8, 14, 22
Toate valorile sunt aranjate în ordine crescătoare. Acum, vom observa cum va arăta coada de prioritate după efectuarea următoarelor operațiuni:
Tipuri de coadă prioritară
Există două tipuri de coadă de prioritate:
Reprezentarea cozii de prioritate
Acum, vom vedea cum să reprezentăm coada de prioritate printr-o listă unidirecțională.
Vom crea coada de prioritate folosind lista de mai jos în care INFO lista conține elementele de date, PRN lista conține numerele de prioritate ale fiecărui element de date disponibil în INFO listă, iar LINK conține practic adresa următorului nod.
Să creăm coada de prioritate pas cu pas.
ștergerea cache-ului npm
În cazul cozii cu prioritate, numărul cu prioritate mai mică este considerat cu prioritate mai mare, adică număr cu prioritate mai mică = prioritate mai mare.
Pasul 1: În listă, numărul cu prioritate inferioară este 1, a cărui valoare a datelor este 333, deci va fi inserat în listă așa cum se arată în diagrama de mai jos:
Pasul 2: După introducerea 333, numărul de prioritate 2 are o prioritate mai mare, iar valorile datelor asociate cu această prioritate sunt 222 și 111. Deci, aceste date vor fi inserate pe baza principiului FIFO; prin urmare, se vor adăuga mai întâi 222 și apoi 111.
Pasul 3: După introducerea elementelor de prioritate 2, următorul număr de prioritate mai mare este 4 și elementele de date asociate cu 4 numere de prioritate sunt 444, 555, 777. În acest caz, elementele ar fi inserate pe baza principiului FIFO; prin urmare, se vor adăuga mai întâi 444, apoi 555 și apoi 777.
Pasul 4: După introducerea elementelor de prioritate 4, următorul număr de prioritate mai mare este 5, iar valoarea asociată priorității 5 este 666, deci va fi inserat la sfârșitul cozii.
Implementarea Cozii prioritare
Coada de prioritate poate fi implementată în patru moduri, care includ matrice, listă legată, structura de date heap și arbore de căutare binar. Structura de date heap este cea mai eficientă modalitate de implementare a cozii de prioritate, așa că vom implementa coada de prioritate folosind o structură de date heap în acest subiect. Acum, mai întâi înțelegem motivul pentru care heap-ul este cel mai eficient mod dintre toate celelalte structuri de date.
Analiza complexităților folosind diferite implementări
| Implementarea | adăuga | Elimina | arunca o privire |
| Lista legată | O(1) | Pe) | Pe) |
| Morman binar | O(logn) | O(logn) | O(1) |
| Arborele de căutare binar | O(logn) | O(logn) | O(1) |
Ce este Heap?
Un heap este o structură de date bazată pe arbore care formează un arbore binar complet și satisface proprietatea heap. Dacă A este un nod părinte al lui B, atunci A este ordonat în raport cu nodul B pentru toate nodurile A și B dintr-un heap. Înseamnă că valoarea nodului părinte poate fi mai mare sau egală cu valoarea nodului copil, sau valoarea nodului părinte poate fi mai mică sau egală cu valoarea nodului copil. Prin urmare, putem spune că există două tipuri de grămezi:
Ambele grămezi sunt heap binar, deoarece fiecare are exact două noduri copil.
Operații prioritare în coadă
Operațiunile comune pe care le putem efectua într-o coadă prioritară sunt inserarea, ștergerea și vizualizarea. Să vedem cum putem menține structura de date heap.
Dacă introducem un element într-o coadă de prioritate, acesta se va muta în slotul gol privind de sus în jos și de la stânga la dreapta.
subliniați în markdown
Dacă elementul nu este într-un loc corect, atunci este comparat cu nodul părinte; dacă se găsește neregulat, elementele sunt schimbate. Acest proces continuă până când elementul este plasat într-o poziție corectă.
După cum știm că într-un heap maxim, elementul maxim este nodul rădăcină. Când eliminăm nodul rădăcină, acesta creează un slot gol. Ultimul element inserat va fi adăugat în acest slot gol. Apoi, acest element este comparat cu nodurile copil, adică copilul stâng și copilul drept, și se schimbă cu cel mai mic dintre cele două. Continuă să se miște în jos în copac până când proprietatea heap este restaurată.
Aplicații de coadă de prioritate
Următoarele sunt aplicațiile cozii de prioritate:
- Este folosit în algoritmul cu calea cea mai scurtă a lui Dijkstra.
- Este folosit în algoritmul lui prim
- Este folosit în tehnici de compresie a datelor, cum ar fi codul Huffman.
- Este folosit în sortarea grămezilor.
- Este, de asemenea, utilizat în sistemele de operare, cum ar fi programarea priorităților, echilibrarea sarcinii și gestionarea întreruperilor.
Program pentru a crea coada de prioritate folosind heap-ul maxim binar.
#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])>