实现一个优先级队列

问题：怎样实现一个按优先级排序的队列？并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素

解决方案：利用 heapq 模块

 1 # priority queue algorithm
 2 
 3 # This module provides an implementaion of the heap algorithm
 4 import heapq 
 5 
 6 # This class provides priority queue algorithm
 7 class PriorityQueue:
 8     def __init__(self):
 9         self._queue = []
10         self._index = ()
11         
12     def push(self, item, priority):
13         heapq.heappush(self._queue, (-priority, self._index, item))
14         self._index += 1
15         
16     def pop(self):
17         return heapq.heappop(self._queue)[-1]
18         
19         
20 class Item:
21     def __init__(self, name):
22         self.name = name
23         
24     def __repr__(self):
25         return 'Item({!r})'.format(self.name)
26         
27         
28 """
29 操作结果
30 >>> q = PriorityQueue()
31 >>> q.push(Item('foo'), 1)
32 >>> q.push(Item('bar'), 5)
33 >>> q.push(Item('spam'), 4)
34 >>> q.push(Item('grok'), 1)
35 >>> q.pop()
36 Item('bar')
37 >>> q.pop()
38 Item('spam')
39 >>> q.pop()
40 Item('foo')
41 >>> q.pop()
42 Item('grok')
43 >>>
44 """
45

View Code

函数 heapq.heappush() 和 heapq.heappop() 分别在队列 _queue 上插入和删除第一个元素，并且队列 _queue 保证第一个元素拥有最高优先级。

heappop() 函数总是返回”最小的”的元素，这就是保证队列 pop 操作返回正确元素的关键。另外，由于 push 和 pop操作时间复杂度为 O(log N)，

其中 N 是堆的大小，因此就算是 N 很大的时候它们运行速度也依旧很快。在上面代码中，队列包含了一个 (-priority, index, item) 的元组。优先级

为负数的目的是使得元素按照优先级从高到低排序。这个跟普通的按优先级从低到高排序的堆排序恰巧相反。index 变量的作用是保证同等优先级

元素的正确排序。通过保存一个不断增加的index 下标变量，可以确保元素按照它们插入的顺序排序。而且， index 变量也在相同优先级元素

比较的时候起到重要作用。