So implementieren Sie die Prioritätswarteschlange in Python (mit Code)

In diesem Artikel geht es darum, wie Python Prioritätswarteschlangen implementiert (mit Code). Freunde in Not können sich darauf beziehen.

1. Anforderungen

Wir möchten eine Warteschlange implementieren, die Elemente mit einer bestimmten Priorität sortieren und das Element mit der höchsten Priorität für jedes Element zurückgeben kann

2. Lösung

Verwenden Sie das Heapq-Modul zur Implementierung

Code:

import heapq

#利用heapq实现一个简答的优先级队列
class PriorityQueue:
    def __init__(self):
        self._queue=[]
        self._index=0
    def push(self,item,priority):
        heapq.heappush(self._queue,(-priority,self._index,item))
        self._index+=1
    def pop(self):
        return heapq.heappop(self._queue)[-1]

class Item:
    def __init__(self,name):
        self.name=name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    q=PriorityQueue()
    q.push(Item('foo'),1)
    q.push(Item('bar'),5)
    q.push(Item('spam'),4)
    q.push(Item('grok'),1)

    print(q.pop())
    print(q.pop())
    #具有相同优先级的两个元素，返回的顺序同它们插入到队列时的顺序相同
    print(q.pop())
    print(q.pop())

Laufergebnis:

Item('bar')
Item('spam')
Item('foo')
Item('grok')

Der Kern des obigen Codes liegt in der Verwendung des Heapq-Moduls. Die Funktionen heapq.heapqpush() und heapq.heapqpop() implementieren das Einfügen bzw. Entfernen von Elementen aus der Liste _queue und stellen sicher, dass das erste Element in der Liste die niedrigste Priorität hat. Die Methode heappop() gibt immer das [kleinste] Element zurück, daher ist dies der Schlüssel zum Entfernen des richtigen Elements aus der Warteschlange. Da die Komplexität von Push- und Pop-Operationen außerdem O (logN) beträgt, wobei N die Anzahl der Elemente im Heap darstellt, ist die Effizienz dieser Operationen auch bei großem N-Wert sehr hoch.

Im obigen Code besteht die Warteschlange aus Tupeln (-Priorität, Index, Element). Der Zweck der Annahme eines negativen Werts für die Priorität besteht darin, die Warteschlange entsprechend der Priorität der Elemente in der Reihenfolge von hoch nach niedrig anzuordnen.

Die Funktion des Variablenindex besteht darin, Elemente mit derselben Priorität in der entsprechenden Reihenfolge anzuordnen. Durch die Pflege eines ständig wachsenden Indexes werden die Elemente in der Reihenfolge angeordnet, in der sie in der Warteschlange erscheinen. Um die Rolle des Index zu veranschaulichen, sehen Sie sich das folgende Beispiel an:

Code:

class Item:
    def __init__(self,name):
        self.name=name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    a=(1,Item('foo'))
    b=(5,Item('bar'))
    #下面一句打印True
    print(a<b)


    c=(1,Item('grok'))
    #下面一句会报错：TypeError: '<' not supported between instances of 'Item' and 'Item'
    print(c<a)


    d=(1,0,Item('foo'))
    e=(5,1,Item('bar'))
    f=(1,2,Item('grok'))
    #下面一句打印True
    print(d<e)
    #下面一句打印True
    print(d<f)

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Prioritätswarteschlange in Python (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!