Coada prioritară în Python
Cozi prioritare sunt structuri de date abstracte în care fiecare dată/valoare din coadă are o anumită prioritate. De exemplu, în companiile aeriene, bagajele cu titlul Business sau First-class ajung mai devreme decât restul.
Priority Queue este o extensie a cozii cu următoarele proprietăți.
- Un element cu prioritate mare este scos din coadă înaintea unui element cu prioritate scăzută.
- Dacă două elemente au aceeași prioritate, acestea sunt servite în funcție de ordinea lor în coadă.
Variat aplicatii din coada de priorități în informatică sunt:
Algoritmi de planificare a joburilor, programare CPU și disc, gestionarea resurselor care sunt partajate între diferite procese etc.
Diferențele esențiale dintre Coada prioritară și Coadă de așteptare:
- În coadă, cel mai vechi element este scos din coadă mai întâi. În timp ce, în Priority Queue, un element bazat pe cea mai mare prioritate este scos din coadă.
- Când elementele sunt scoase dintr-o coadă de prioritate, rezultatul obținut este fie sortat în ordine crescătoare, fie în ordine descrescătoare. În timp ce, atunci când elementele sunt scoase dintr-o coadă simplă, se obține o ordine FIFO a datelor în rezultat.
Mai jos este a implementare simplă a cozii de prioritate.
Piton
# 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]>>>> :> > myQueue> => PriorityQueue()> > myQueue.insert(> 12> )> > myQueue.insert(> 1> )> > myQueue.insert(> 14> )> > myQueue.insert(> 7> )> > print> (myQueue)> > while> not> myQueue.isEmpty():> > print> (myQueue.delete())> |
Ieșire:
12 1 14 7 14 12 7 1
Rețineți că complexitatea de timp a ștergerii este O(n) în codul de mai sus. A implementare mai bună este de a folosi Heap binar care este de obicei folosit pentru a implementa o coadă de prioritate. Rețineți că Python oferă heapq si in biblioteca.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
