Cua de prioritats en Python
Cues de prioritat són estructures de dades abstractes on cada dada/valor de la cua té una certa prioritat. Per exemple, a les companyies aèries, l'equipatge amb el títol Business o First class arriba abans que la resta.
Priority Queue és una extensió de la cua amb les propietats següents.
- Un element amb prioritat alta es retira de la cua abans d'un element amb prioritat baixa.
- Si dos elements tenen la mateixa prioritat, es serveixen segons el seu ordre a la cua.
Diversos aplicacions de la cua de prioritats en Informàtica són:
Algorismes de Job Scheduling, CPU i Disk Scheduling, gestió de recursos que es comparteixen entre diferents processos, etc.
Diferències clau entre la cua de prioritat i la cua:
- A la cua, primer es retira l'element més antic. Mentre que, a la cua de prioritats, un element basat en la prioritat més alta es retira de la cua.
- Quan surten elements d'una cua de prioritats, el resultat obtingut s'ordena en ordre creixent o en ordre decreixent. Mentre que, quan es treuen elements d'una cua simple, s'obté un ordre FIFO de dades en el resultat.
A continuació hi ha a implementació senzilla de la cua de prioritats.
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())> |
Sortida:
12 1 14 7 14 12 7 1
Tingueu en compte que la complexitat temporal de la supressió és O(n) al codi anterior. A millor implementació és utilitzar Munt binari que normalment s'utilitza per implementar una cua de prioritats. Tingueu en compte que Python proporciona heapq també a la biblioteca.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
