Prioriterte køer er abstrakte datastrukturer hvor hver data/verdi i køen har en viss prioritet. For eksempel hos flyselskaper kommer bagasje med tittelen Business eller First-class tidligere enn resten.
Priority Queue er en utvidelse av køen med følgende egenskaper.
- Et element med høy prioritet settes ut av kø før et element med lav prioritet.
- Hvis to elementer har samme prioritet, serveres de i henhold til rekkefølgen i køen.
Diverse applikasjoner av prioritetskøen i informatikk er:
Jobbplanleggingsalgoritmer, CPU- og diskplanlegging, administrasjon av ressurser som deles mellom ulike prosesser, etc.
Viktige forskjeller mellom Priority Queue og Queue:
- I kø blir det eldste elementet satt ut av kø først. Mens, i Priority Queue, blir et element basert på høyeste prioritet satt ut av kø.
- Når elementer hoppes ut av en prioritert kø, blir resultatet enten sortert i økende rekkefølge eller i synkende rekkefølge. Mens, når elementer poppes fra en enkel kø, oppnås en FIFO-rekkefølge med data i resultatet.
Nedenfor er en enkel implementering av prioritert kø.
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())> |
>
>Produksjon:
12 1 14 7 14 12 7 1>
Merk at tidskompleksiteten for sletting er O(n) i koden ovenfor. EN bedre gjennomføring er å bruke Binær haug som vanligvis brukes til å implementere en prioritert kø. Merk at Python gir heapq på biblioteket også.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))>