43 lines
1.3 KiB
Python
43 lines
1.3 KiB
Python
import heapq
|
||
|
||
|
||
# 优先级队列（使用小根堆实现）
|
||
class PriorityQueue:
|
||
def __init__(self):
|
||
self._queue = []
|
||
# 由于优先级在比较大小时可能相同造成比较失败，维护一个下标index来进行二级辨识
|
||
self._index = 0
|
||
|
||
# 由于heapq的原理是生成一个小根堆，所以优先级取负，这样优先级越大，堆识别到的优先级越小；引入index，在优先级相同时比较入栈先后顺序
|
||
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]
|
||
|
||
|
||
# 在Python中，实例化对象是不可以直接进行比较的，例如：
|
||
class Item:
|
||
def __init__(self, name):
|
||
self.name = name
|
||
|
||
def __repr__(self):
|
||
|
||
return 'Item {!r}'.format(self.name)
|
||
# a = Iter('foo') b = Iter('bar'), 进行a<b比较会输出报错
|
||
|
||
# 一个优先级队列的简单调用示例
|
||
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)
|
||
a = q.pop()
|
||
b = q.pop()
|
||
c = q.pop()
|
||
d = q.pop()
|
||
print(a)
|
||
|