logo

Prioritetskø i Python

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.



  1. Et element med høy prioritet settes ut av kø før et element med lav prioritet.
  2. 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:

  1. 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ø.
  2. 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))>