Prioritätswarteschlange in Python
Prioritätswarteschlangen sind abstrakte Datenstrukturen, bei denen alle Daten/Werte in der Warteschlange eine bestimmte Priorität haben. Beispielsweise kommt bei Fluggesellschaften Gepäck mit der Bezeichnung Business oder First Class früher an als der Rest.
Die Prioritätswarteschlange ist eine Erweiterung der Warteschlange mit den folgenden Eigenschaften.
- Ein Element mit hoher Priorität wird vor einem Element mit niedriger Priorität aus der Warteschlange entfernt.
- Wenn zwei Elemente die gleiche Priorität haben, werden sie entsprechend ihrer Reihenfolge in der Warteschlange bedient.
Verschieden Anwendungen der Prioritätswarteschlange in Informatik sind:
Jobplanungsalgorithmen, CPU- und Festplattenplanung, Verwaltung von Ressourcen, die von verschiedenen Prozessen gemeinsam genutzt werden usw.
Hauptunterschiede zwischen Priority Queue und Queue:
- In der Warteschlange wird das älteste Element zuerst aus der Warteschlange entfernt. Während in der Prioritätswarteschlange ein Element mit der höchsten Priorität aus der Warteschlange entfernt wird.
- Wenn Elemente aus einer Prioritätswarteschlange entfernt werden, wird das erhaltene Ergebnis entweder in aufsteigender oder absteigender Reihenfolge sortiert. Wenn hingegen Elemente aus einer einfachen Warteschlange entnommen werden, wird im Ergebnis eine FIFO-Reihenfolge der Daten erhalten.
Unten ist ein einfache Umsetzung der Prioritätswarteschlange.
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())> |
Ausgabe:
12 1 14 7 14 12 7 1
Beachten Sie, dass die zeitliche Komplexität des Löschens im obigen Code O(n) beträgt. A bessere Umsetzung ist zu verwenden Binärer Heap Dies wird normalerweise zur Implementierung einer Prioritätswarteschlange verwendet. Beachten Sie, dass Python bereitstellt Heapq auch in der Bibliothek.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
