本文最后更新于:2021年11月14日 凌晨
有时候会不可避免的用到优先级队列,根据优先级来决定调度,这一点在事件监听器中非常常见。
如何用 Python
实现优先级队列?
Python
有个标准库模块 heapq
,这个模块提供了堆队列的相关操作。
简单来说,就是利用了 heapq
的堆队列,构造了一个优先级队列。并利用迭代来逐个获取元素,从而达到 priority
越小越优先的效果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| from typing import NoReturn, Any, NewType, Iterator import heapq
class PriorityQueue(Iterator): T = NewType('T', Any)
def __init__(self): self.queue = [] self.index = 0
def join(self, item: T, priority: int) -> NoReturn: heapq.heappush(self.queue, (priority, self.index, item)) self.index += 1
def __next__(self) -> T: if self.queue: return heapq.heappop(self.queue)[-1] else: raise StopIteration @property def first(self) -> T: return heapq.heappop(self.queue)[-1]
|