以下python程序使用该heapq
模块实现简单的优先级队列:
$title(PriorityQueue.py)
import 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]
让我们看一个如何使用上面创建的优先级队列的例子。
$title(example.py)
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
>>> q = PriorityQueue()
>>> q.push(Item('l'), 1)
>>> q.push(Item('e'), 5)
>>> q.push(Item('f'), 4)
>>> q.push(Item('t'), 2)
>>> q.push(Item('so'), 1)
>>> q.pop()
Item('e') #5
>>> q.pop()
Item('f') #4
>>> q.pop()
Item('t') #2
>>> q.pop()
Item('l') #1
>>> q.pop()
Item('so') #1
https://www.leftso.com/article/738.html