Pythoncookbook（数据结构与算法）实现优先级队列的方法示例-创新互联

本文实例讲述了Python实现优先级队列的方法。分享给大家供大家参考，具体如下：

问题：要实现一个队列，它能够以给定的优先级对元素排序，且每次pop操作时都会返回优先级最高的那个元素；

解决方案：采用heapq模块实现一个简单的优先级队列

# example.py
#
# Example of a priority queue
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]
# Example use
class Item:
  def __init__(self, name):
    self.name = name
  def __repr__(self):
    return 'Item({!r})'.format(self.name)
q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)
print("Should be bar:", q.pop())
print("Should be spam:", q.pop())
print("Should be foo:", q.pop())
print("Should be grok:", q.pop())