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)
|
|||
|
|
|