Prednostne čakalne vrste so abstraktne podatkovne strukture, kjer ima vsak podatek/vrednost v čakalni vrsti določeno prioriteto. Na primer, pri letalskih družbah prtljaga z naslovom Business ali First-class prispe prej kot ostala.
Prednostna čakalna vrsta je razširitev čakalne vrste z naslednjimi lastnostmi.
- Element z visoko prioriteto je izključen iz čakalne vrste pred elementom z nizko prioriteto.
- Če imata dva elementa enako prioriteto, se strežeta glede na njihov vrstni red v čakalni vrsti.
Različno aplikacije prednostne čakalne vrste v računalništvu so:
Algoritmi za razporejanje opravil, razporejanje procesorja in diska, upravljanje virov, ki se delijo med različnimi procesi itd.
Ključne razlike med prednostno čakalno vrsto in čakalno vrsto:
java nizi
- V čakalni vrsti je najstarejši element najprej izključen iz čakalne vrste. Medtem ko je v prednostni čakalni vrsti element, ki temelji na najvišji prioriteti, izključen iz čakalne vrste.
- Ko so elementi izrinjeni iz prednostne čakalne vrste, je dobljeni rezultat razvrščen v naraščajočem ali padajočem vrstnem redu. Medtem ko se elementi odstranijo iz preproste čakalne vrste, se v rezultatu pridobi vrstni red podatkov FIFO.
Spodaj je a enostavna izvedba prednostne čakalne vrste.
Python
java vsebuje podniz
# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(>object>):> >def> __init__(>self>):> >self>.queue>=> []> >def> __str__(>self>):> >return> ' '>.join([>str>(i)>for> i>in> self>.queue])> ># for checking if the queue is empty> >def> isEmpty(>self>):> >return> len>(>self>.queue)>=>=> 0> ># for inserting an element in the queue> >def> insert(>self>, data):> >self>.queue.append(data)> ># for popping an element based on Priority> >def> delete(>self>):> >try>:> >max_val>=> 0> >for> i>in> range>(>len>(>self>.queue)):> >if> self>.queue[i]>>self>.queue[max_val]:> >max_val>=> i> >item>=> self>.queue[max_val]> >del> self>.queue[max_val]> >return> item> >except> IndexError:> >print>()> >exit()> if> __name__>=>=> '__main__'>:> >myQueue>=> PriorityQueue()> >myQueue.insert(>12>)> >myQueue.insert(>1>)> >myQueue.insert(>14>)> >myQueue.insert(>7>)> >print>(myQueue)> >while> not> myQueue.isEmpty():> >print>(myQueue.delete())> |
>
>Izhod:
aes proti des
12 1 14 7 14 12 7 1>
Upoštevajte, da je časovna kompleksnost brisanja O(n) v zgornji kodi. A boljša izvedba je za uporabo Binarna kopica ki se običajno uporablja za implementacijo prednostne čakalne vrste. Upoštevajte, da Python ponuja heapq tudi v knjižnici.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))>