Prednostna čakalna vrsta v Pythonu
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:
- 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
# 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:
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))
