2.2.7 实现优先级队列
在Python程序中，使用内置模块heapq可以实现一个简单的优先级队列。下面的实例文件youxianpy.py演示了实现一个简单的优先级队列的过程。
源码路径：daima\第2章\youxianpy.py
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)
q = PriorityQueue()
q.push(Item('AAA'), 1)
q.push(Item('BBB'), 4)
q.push(Item('CCC'), 5)
q.push(Item('DDD'), 1)
print(q.pop())
print(q.pop())
print(q.pop())
在上述代码中，利用heapq模块实现了一个简单的优先级队列，第一次执行pop()操作时返回的元素具有最高的优先级。拥有相同优先级的两个元素（foo和grok）返回的顺序，同插入到队列时的顺序相同。函数heapq.heappush()和heapq.heappop()分别实现了列表_queue中元素的插入和移除操作，并且保证列表中第一个元素的优先级最低。函数heappop()总是返回“最小”的元素，并且因为push和pop操作的复杂度都是O(log2N)，其中N代表堆中元素的数量，因此就算N的值很大，这些操作的效率也非常高。上述代码中的队列以元组（−priority, index, item）的形式组成，priority取负值是为了让队列能够按元素的优先级从高到低排列。这和正常的堆排列顺序相反，一般情况下，堆是按从小到大的顺序进行排序的。变量index的作用是将具有相同优先级的元素以适当的顺序排列。通过维护一个不断递增的索引，元素将以它们加入队列时的顺序排列。但是当index在对具有相同优先级的元素间进行比较操作时，同样扮演一个重要的角色。执行结果如图2-17所示。
图2-17 执行结果
在Python程序中，如果以元组（priority, item）的形式存储元素，只要它们的优先级不同，它们就可以进行比较。但是如果两个元组的优先级相同，在进行比较操作时会失败。这时可以考虑引入一个额外的索引值，以（priority, index, item）的方式建立元组，因为没有哪两个元组会有相同的index值，所以这样就可以完全避免上述问题。一旦比较操作的结果可以确定，Python就不会再去比较剩下的元组元素了。下面的实例文件suoyin.py演示了实现一个简单的优先级队列的过程。
源码路径：daima\第2章\suoyin.py
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)
①a = Item('AAA')
b = Item('BBB')
#a < b 错误
a = (1, Item('AAA'))
b = (5, Item('BBB'))
print(a < b)
c = (1, Item('CCC'))
②#a < c 错误
③a = (1, 0, Item('AAA'))
b = (5, 1, Item('BBB'))
c = (1, 2, Item('CCC'))
print(a < b)
④print(a < c)
在上述代码中，因为在①～②中没有添加索引，所以当两个元组的优先级相同时会出错；而在③～④中添加了索引，这样就不会出错了。执行结果如图2-18所示。
图2-18 执行结果