Coda prioritaria in Python
Code prioritarie sono strutture di dati astratte in cui ogni dato/valore in coda ha una certa priorità. Ad esempio, nelle compagnie aeree, i bagagli con il titolo Business o First class arrivano prima degli altri.
Priority Queue è un'estensione della coda con le seguenti proprietà.
- Un elemento con priorità alta viene rimosso dalla coda prima di un elemento con priorità bassa.
- Se due elementi hanno la stessa priorità, verranno serviti secondo il loro ordine in coda.
Vari applicazioni della coda di Priorità in Informatica sono:
Algoritmi di pianificazione dei lavori, pianificazione della CPU e del disco, gestione delle risorse condivise tra diversi processi, ecc.
Differenze chiave tra coda prioritaria e coda:
- In Queue, l'elemento più vecchio viene rimosso per primo. Mentre, in Priority Queue, un elemento basato sulla priorità più alta viene rimosso dalla coda.
- Quando gli elementi vengono estratti da una coda di priorità, il risultato ottenuto viene ordinato in ordine crescente o in ordine decrescente. Mentre, quando gli elementi vengono estratti da una coda semplice, nel risultato si ottiene un ordine FIFO dei dati.
Di seguito è riportato un semplice implementazione della coda prioritaria.
Pitone
# 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())> |
Produzione:
12 1 14 7 14 12 7 1
Si noti che la complessità temporale dell'eliminazione è O(n) nel codice precedente. UN migliore implementazione è usare Heap binario che viene tipicamente utilizzato per implementare una coda di priorità. Nota che Python fornisce heapq anche in biblioteca.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
