TechCodeview

Prioritetni red čekanja je apstraktni tip podataka koji se ponaša slično normalnom redu čekanja osim što svaki element ima određeni prioritet, tj. element s najvišim prioritetom bio bi prvi u redu čekanja prioriteta. Prioritet elemenata u redu čekanja prioriteta odredit će redoslijed kojim se elementi uklanjaju iz reda čekanja prioriteta.

Prioritetni red podržava samo usporedive elemente, što znači da su elementi poredani uzlaznim ili silaznim redoslijedom.

ručno testiranje

Na primjer, pretpostavimo da imamo neke vrijednosti poput 1, 3, 4, 8, 14, 22 umetnute u red prioriteta s redoslijedom nametnutim vrijednostima od najmanjeg do najvećeg. Stoga bi broj 1 imao najveći prioritet, dok bi broj 22 imao najniži prioritet.

Karakteristike prioritetnog reda čekanja

Prioritetni red je proširenje reda koji sadrži sljedeće karakteristike:

• Svaki element u redu prioriteta ima neki prioritet koji mu je pridružen.
• Element s višim prioritetom bit će izbrisan prije brisanja elementa s nižim prioritetom.
• Ako dva elementa u redu prioriteta imaju isti prioritet, oni će biti raspoređeni prema FIFO principu.

Razmotrimo prioritetni red kroz primjer.

Imamo prioritetni red koji sadrži sljedeće vrijednosti:

1, 3, 4, 8, 14, 22

Sve vrijednosti poredane su uzlaznim redoslijedom. Sada ćemo promatrati kako će prioritetni red čekanja izgledati nakon izvođenja sljedećih operacija:

anketa():Ova funkcija će ukloniti element najvišeg prioriteta iz reda prioriteta. U gornjem redu čekanja prioriteta element '1' ima najviši prioritet, pa će biti uklonjen iz reda čekanja prioriteta.dodati (2):Ova funkcija će umetnuti element '2' u prioritetni red. Kako je 2 najmanji element među svim brojevima, on će imati najveći prioritet.anketa():Uklonit će element '2' iz reda čekanja jer ima najviši prioritet.dodati (5):Umetnut će element 5 nakon 4 jer je 5 veći od 4 i manji od 8, pa će dobiti treći najviši prioritet u redu čekanja.

Vrste prioritetnog reda

Postoje dvije vrste prioritetnog reda:

Red čekanja uzlaznim redoslijedom prioriteta:U redu čekanja uzlaznog redoslijeda prioriteta, niži broj prioriteta daje se kao viši prioritet u prioritetu. Na primjer, uzimamo brojeve od 1 do 5 poredane uzlaznim redoslijedom poput 1,2,3,4,5; stoga je najmanji broj, tj. 1 dan kao najviši prioritet u redu čekanja.
Silazni red prioriteta:U redu reda prioriteta silaznog redoslijeda, broj višeg prioriteta daje se kao viši prioritet u prioritetu. Na primjer, uzimamo brojeve od 1 do 5 poredane silaznim redoslijedom kao što su 5, 4, 3, 2, 1; stoga je najveći broj, tj. 5 dan kao najviši prioritet u redu čekanja.

Prikaz prioritetnog reda čekanja

Sada ćemo vidjeti kako prikazati prioritetni red kroz jednosmjernu listu.

Stvorit ćemo prioritetni red koristeći dolje naveden popis u kojem INFO popis sadrži elemente podataka, PRN popis sadrži brojeve prioriteta svakog elementa podataka dostupnog u INFO popis, a LINK u osnovi sadrži adresu sljedećeg čvora.

Kreirajmo prioritetni red čekanja korak po korak.

java sort arraylist

U slučaju reda prioriteta, broj nižeg prioriteta smatra se višim prioritetom, tj. niži broj prioriteta = viši prioritet.

Korak 1: Na popisu je broj nižeg prioriteta 1, čija je vrijednost podataka 333, pa će biti umetnut u popis kao što je prikazano na donjem dijagramu:

Korak 2: Nakon umetanja 333, prioritet broj 2 ima viši prioritet, a vrijednosti podataka pridružene ovom prioritetu su 222 i 111. Dakle, ovi podaci će biti umetnuti na temelju FIFO principa; stoga će se prvo dodati 222, a zatim 111.

Korak 3: Nakon umetanja elemenata prioriteta 2, sljedeći viši broj prioriteta je 4, a elementi podataka povezani s 4 broja prioriteta su 444, 555, 777. U ovom slučaju, elementi bi bili umetnuti na temelju FIFO principa; dakle, prvo će se dodati 444, zatim 555, a zatim 777.

Korak 4: Nakon umetanja elemenata prioriteta 4, sljedeći broj višeg prioriteta je 5, a vrijednost povezana s prioritetom 5 je 666, tako da će biti umetnut na kraj reda čekanja.

Implementacija prioritetnog reda

Prioritetni red čekanja može se implementirati na četiri načina koji uključuju nizove, povezane liste, strukturu podataka hrpe i binarno stablo pretraživanja. Struktura podataka gomile najučinkovitiji je način implementacije prioritetnog reda, stoga ćemo u ovoj temi implementirati prioritetni red pomoću strukture podataka gomile. Sada, prvo razumijemo razlog zašto je heap najučinkovitiji način među svim ostalim strukturama podataka.

Analiza složenosti pomoću različitih implementacija

Što je Heap?

Hrpa je podatkovna struktura temeljena na stablu koja tvori potpuno binarno stablo i zadovoljava svojstvo hrpe. Ako je A nadređeni čvor B, tada je A poredan u odnosu na čvor B za sve čvorove A i B u gomili. To znači da bi vrijednost nadređenog čvora mogla biti veća ili jednaka vrijednosti podređenog čvora, ili bi vrijednost nadređenog čvora mogla biti manja ili jednaka vrijednosti podređenog čvora. Stoga možemo reći da postoje dvije vrste gomila:

Maksimalna gomila:Maksimalna gomila je gomila u kojoj je vrijednost nadređenog čvora veća od vrijednosti podređenih čvorova.
Min. gomila:Min heap je hrpa u kojoj je vrijednost nadređenog čvora manja od vrijednosti podređenih čvorova.

Obje hrpe su binarne hrpe, jer svaka ima točno dva podređena čvora.

Prioritetne operacije čekanja

Uobičajene operacije koje možemo izvesti na prioritetnom redu čekanja su umetanje, brisanje i provirivanje. Pogledajmo kako možemo održavati strukturu podataka gomile.

Umetanje elementa u prioritetni red čekanja (maks. gomila)

Ako umetnemo element u prioritetni red čekanja, on će se pomaknuti na prazan utor gledajući odozgo prema dolje i slijeva nadesno.

java izjava o slučaju

Ako element nije na ispravnom mjestu tada se uspoređuje s nadređenim čvorom; ako se utvrdi da nije u redu, elementi se mijenjaju. Ovaj proces se nastavlja sve dok se element ne postavi u pravilan položaj.

Uklanjanje minimalnog elementa iz reda prioriteta

Kao što znamo da je u maksimalnoj hrpi najveći element korijenski čvor. Kada uklonimo korijenski čvor, on stvara prazan utor. Posljednji umetnuti element bit će dodan u ovaj prazan utor. Zatim se ovaj element uspoređuje s podređenim čvorovima, tj. lijevim podređenim i desnim podređenim elementom, i zamijeni s manjim od ta dva. Nastavlja se kretati niz stablo dok se svojstvo hrpe ne obnovi.

Prijave prioritetnog reda čekanja

Sljedeće su aplikacije prioritetnog reda:

• Koristi se u Dijkstrinom algoritmu najkraćeg puta.
• Koristi se u prim algoritmu
• Koristi se u tehnikama kompresije podataka kao što je Huffmanov kod.
• Koristi se u heap sortiranju.
• Također se koristi u operacijskom sustavu kao što je planiranje prioriteta, balansiranje opterećenja i rukovanje prekidima.

Program za stvaranje prioritetnog reda pomoću binarne maksimalne hrpe.

 #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])>