Python教程-Python queue 队列优先级

1.什么是队列优先级

• 队列优先级是一种抽象数据类型，类似于常规队列或堆栈数据结构，但每个元素另外都具有与之关联的“优先级”。
• 在优先级队列中，优先级高的元素先于优先级低的元素提供。
• 如果两个元素具有相同的优先级，则将根据它们在队列中的顺序为其提供服务。

2. Python中的队列优先级实现

以下python程序使用该heapq模块实现简单的优先级队列：

$title(PriorityQueue.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]

3. Python队列优先级示例

让我们看一个如何使用上面创建的优先级队列的例子。

$title(example.py)
class Item:
    def __init__(self, name):
        self.name = name
    def __repr__(self):
        return 'Item({!r})'.format(self.name)
 
>>> q = PriorityQueue()
 
>>> q.push(Item('l'), 1)
>>> q.push(Item('e'), 5)
>>> q.push(Item('f'), 4)
>>> q.push(Item('t'), 2)
>>> q.push(Item('so'), 1)
 
>>> q.pop()
Item('e')      #5
 
>>> q.pop()
Item('f')      #4
 
>>> q.pop()
Item('t')      #2
 
>>> q.pop()
Item('l')     #1
 
>>> q.pop()
Item('so')    #1