如何实现一个优先级队列

如何实现一个优先级队列

模块

heapq

代码

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
34
35
36
37
38
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]


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

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


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

if __name__ == '__main__':
main()

第一个 pop()操作返回优先级最高的元素。 另外注意到如果两个有 着相同优先级的元素( foogrok ),pop操作按照它们被插入到队列的顺序返回的

Pycharm追踪

加入断点

加入断点

push操作

加入4个元组

pop操作

执行pop操作

最先优先级别bar出队列

执行结果

执行结果

结论

  1. 函数 heapq.heappush()heapq.heappop() 分别在队列 _queue 上插入和删除第一个元素
  2. heappop()总是返回最小的元素,这是保证队列pop操作返回正确元素的关键
  3. pushpop的时间复杂度为O(N),所以就算N很大,运行速度也很快
  4. (-priority, index, item),优先级为负数的原因就是使得元素按照优先级从高到低排序
  5. index变量的作用是保证同等优先级元素的正确排序,其实就是插入顺序

注:本文使用的实例代码,参考自《python cookbook 第三版》