Prioriterade köer är abstrakta datastrukturer där varje data/värde i kön har en viss prioritet. Till exempel hos flygbolag kommer bagage med titeln Business eller First-class tidigare än resten.
Priority Queue är en förlängning av kön med följande egenskaper.
- Ett element med hög prioritet tas ur kö före ett element med låg prioritet.
- Om två element har samma prioritet serveras de enligt deras ordning i kön.
Olika applikationer i prioriteringskön i datavetenskap är:
Job Scheduling algoritmer, CPU och Disk Scheduling, hantering av resurser som delas mellan olika processer, etc.
Viktiga skillnader mellan Priority Queue och Queue:
- I Queue tas det äldsta elementet ur kö först. Medan, i Priority Queue, tas ett element baserat på högsta prioritet ur kö.
- När element tas ut ur en prioriterad kö sorteras resultatet antingen i ökande ordning eller i minskande ordning. Medan, när element poppas från en enkel kö, erhålls en FIFO-ordning av data i resultatet.
Nedan är en enkel implementering av prioritetskön.
Pytonorm
logotyp java
# 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())> |
>
oj koncept
>Produktion:
12 1 14 7 14 12 7 1>
Observera att tidskomplexiteten för radering är O(n) i ovanstående kod. A bättre genomförande är att använda Binär hög som vanligtvis används för att implementera en prioritetskö. Observera att Python tillhandahåller heapq på biblioteket också.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))>