Prednostna čakalna vrsta je abstraktna vrsta podatkov, ki se obnaša podobno kot običajna čakalna vrsta, le da ima vsak element določeno prednost, tj. element z najvišjo prioriteto bi bil prvi v prednostni čakalni vrsti. Prednost elementov v prednostni čakalni vrsti bo določila vrstni red, v katerem bodo elementi odstranjeni iz prednostne čakalne vrste.
Prednostna čakalna vrsta podpira samo primerljive elemente, kar pomeni, da so elementi razvrščeni v naraščajočem ali padajočem vrstnem redu.
java filter tok
Recimo, da imamo nekaj vrednosti, kot so 1, 3, 4, 8, 14, 22, vstavljenih v prednostno čakalno vrsto z vrstnim redom, ki je naložen vrednostim od najmanjše do največje. Zato bi imelo število 1 najvišjo prioriteto, medtem ko bo imelo število 22 najnižjo prednost.
Značilnosti prednostne čakalne vrste
Prednostna čakalna vrsta je razširitev čakalne vrste, ki vsebuje naslednje značilnosti:
- Vsak element v prednostni čakalni vrsti ima določeno prioriteto, povezano z njim.
- Element z višjo prioriteto bo izbrisan pred izbrisom elementa z nižjo prioriteto.
- Če imata dva elementa v prednostni čakalni vrsti enako prioriteto, bosta razporejena po principu FIFO.
Razumejmo prednostno čakalno vrsto na primeru.
Imamo prednostno čakalno vrsto, ki vsebuje naslednje vrednosti:
1, 3, 4, 8, 14, 22
Vse vrednosti so razvrščene v naraščajočem vrstnem redu. Zdaj bomo opazovali, kako bo izgledala prednostna čakalna vrsta po izvedbi naslednjih operacij:
Vrste prednostne čakalne vrste
Obstajata dve vrsti prednostne čakalne vrste:
Predstavitev prednostne čakalne vrste
Zdaj bomo videli, kako predstaviti prednostno čakalno vrsto z enosmernim seznamom.
Ustvarili bomo prednostno čakalno vrsto z uporabo spodnjega seznama, v katerem INFO seznam vsebuje podatkovne elemente, PRN seznam vsebuje prednostne številke vsakega podatkovnega elementa, ki je na voljo v INFO seznam in LINK v bistvu vsebuje naslov naslednjega vozlišča.
Ustvarimo prednostno čakalno vrsto korak za korakom.
java sort arraylist
V primeru prednostne čakalne vrste se nižja prednostna številka šteje za višjo prioriteto, tj. nižja prednostna številka = višja prioriteta.
Korak 1: Na seznamu je nižja prednostna številka 1, katere vrednost podatkov je 333, zato bo vstavljena na seznam, kot je prikazano v spodnjem diagramu:
2. korak: Po vstavitvi 333 ima prednostna številka 2 višjo prioriteto, vrednosti podatkov, povezane s to prioriteto, pa sta 222 in 111. Torej bodo ti podatki vstavljeni na podlagi načela FIFO; zato bo najprej dodano 222 in nato 111.
3. korak: Po vstavitvi elementov prioritete 2 je naslednja višja prednostna številka 4, podatkovni elementi, povezani s 4 prednostnimi številkami, pa so 444, 555, 777. V tem primeru bi bili elementi vstavljeni na podlagi načela FIFO; zato bo najprej dodano 444, nato 555 in nato 777.
4. korak: Po vstavitvi elementov prioritete 4 je naslednja številka višje prioritete 5, vrednost, povezana s prioriteto 5, pa je 666, tako da bo vstavljena na konec čakalne vrste.
Implementacija prednostne čakalne vrste
Prednostno čakalno vrsto je mogoče implementirati na štiri načine, ki vključujejo nize, povezani seznam, podatkovno strukturo kopice in binarno iskalno drevo. Podatkovna struktura kopice je najučinkovitejši način implementacije prednostne čakalne vrste, zato bomo v tej temi implementirali prednostno čakalno vrsto z uporabo podatkovne strukture kopice. Zdaj najprej razumemo razlog, zakaj je kup najučinkovitejši način med vsemi drugimi podatkovnimi strukturami.
Analiza kompleksnosti z različnimi izvedbami
| Izvedba | dodati | Odstrani | pokukati |
| Povezan seznam | O(1) | O(n) | O(n) |
| Binarna kopica | O (prijava) | O (prijava) | O(1) |
| Binarno iskalno drevo | O (prijava) | O (prijava) | O(1) |
Kaj je Heap?
Kopica je drevesna podatkovna struktura, ki tvori popolno binarno drevo in izpolnjuje lastnost kopice. Če je A nadrejeno vozlišče B, potem je A urejeno glede na vozlišče B za vsa vozlišča A in B v kupu. To pomeni, da je lahko vrednost nadrejenega vozlišča večja ali enaka vrednosti podrejenega vozlišča ali pa je vrednost nadrejenega vozlišča lahko manjša ali enaka vrednosti podrejenega vozlišča. Zato lahko rečemo, da obstajata dve vrsti kupov:
Obe kopici sta dvojiški kopici, saj ima vsaka točno dve podrejeni vozlišči.
Operacije prednostne čakalne vrste
Običajne operacije, ki jih lahko izvajamo v prednostni čakalni vrsti, so vstavljanje, brisanje in pokukanje. Poglejmo, kako lahko vzdržujemo podatkovno strukturo kopice.
Če element vstavimo v prednostno čakalno vrsto, se bo premaknil v prazno režo s pogledom od zgoraj navzdol in od leve proti desni.
Če element ni na pravem mestu, se primerja z nadrejenim vozliščem; če se ugotovi, da ni v redu, se elementi zamenjajo. Ta postopek se nadaljuje, dokler element ni nameščen v pravilnem položaju.
Kot vemo, je v največji kopici največji element korensko vozlišče. Ko odstranimo korensko vozlišče, ustvari prazno režo. Zadnji vstavljeni element bo dodan v to prazno režo. Nato se ta element primerja s podrejenimi vozlišči, tj. levim podrejenim in desnim podrejenim elementom, in zamenja z manjšim od obeh. Pomika se navzdol po drevesu, dokler ni obnovljena lastnost kopice.
Aplikacije prednostne čakalne vrste
Sledijo aplikacije prednostne čakalne vrste:
java znak v niz
- Uporablja se v Dijkstrovem algoritmu najkrajše poti.
- Uporablja se v primovem algoritmu
- Uporablja se v tehnikah stiskanja podatkov, kot je Huffmanova koda.
- Uporablja se pri razvrščanju na kup.
- Uporablja se tudi v operacijskem sistemu, kot je prednostno razporejanje, uravnoteženje obremenitve in obravnavanje prekinitev.
Program za ustvarjanje prednostne čakalne vrste z uporabo binarne največje kopice.
#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])>