Prioritetskø i Python
Prioriterede køer er abstrakte datastrukturer, hvor hver data/værdi i køen har en vis prioritet. For eksempel hos flyselskaber ankommer bagage med titlen Business eller First-class tidligere end resten.
Priority Queue er en udvidelse af køen med følgende egenskaber.
- Et element med høj prioritet sættes ud af kø før et element med lav prioritet.
- Hvis to elementer har samme prioritet, serveres de i henhold til deres rækkefølge i køen.
Forskellige applikationer af prioritetskøen i datalogi er:
Jobplanlægningsalgoritmer, CPU- og diskplanlægning, styring af ressourcer, der deles mellem forskellige processer osv.
Vigtigste forskelle mellem Priority Queue og Queue:
- I kø bliver det ældste element sat ud af kø først. Mens et element baseret på den højeste prioritet i Priority Queue bliver sat ud af køen.
- Når elementer springes ud af en prioriteret kø, sorteres det opnåede resultat enten i stigende rækkefølge eller i faldende rækkefølge. Mens, når elementer er poppet fra en simpel kø, opnås en FIFO rækkefølge af data i resultatet.
Nedenfor er en enkel implementering af prioritetskøen.
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())> |
Produktion:
12 1 14 7 14 12 7 1
Bemærk, at tidskompleksiteten for sletning er O(n) i ovenstående kode. EN bedre implementering er at bruge Binær bunke som typisk bruges til at implementere en prioriteret kø. Bemærk, at Python giver heapq også på biblioteket.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
