优先队列 Priority Queue By Python

Python heapq module 提供了堆（优先）队列的实现算法。使用 arrays，heap[k] <= heap[2k + 1]；heap[k] <= heap[2k + 2]，array 起始位置是 0。

参考文献：

1. 用Python实现一个优先级队列（Priority Queue）
2. Python 3.6 Documentation

堆 Heap

堆 heap，是对于每一个父结点上的值都小于或等于子结点的值的二叉树。此外一个堆必须是一个完整的二叉树，除了最低层其它每一级必须是被完整填充的。因此，堆的最重要的一个特点就是：首项 heap[0] 总是最小的一项。（这是 heap 在 Python 中的定义）。

堆化 heapify 则是将一个二叉树转化一个对数据结构的过程。在 Python 中，可以用自带 heapq 模块中的 heapify(x) 函数来实现将一个列表 x 转化为一个堆。时间复杂度为线性 O(N)；linear time。

import heapq
x = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heap = list(x)
heapq.heapify(heap)
heap # [-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]

heap 是指被"堆化"后的列表，heap[0] = -4 为首项，最小项。注意，此时的 heap 的数据类型仍是一个 list，但是可以使用一些堆的方法来进行操作。

可以用 heappop()，heappush()，heapreplace()等方法来对一个堆列表进行操作。例如，heappop() 会从堆列表中拿出并返回最小项，并且使堆保持不变（即 heap[0] 仍为最小项）。

heapq.heappop(heap)  # return -4
heapq.heappop(heap)  # return 1
heapq.heappop(heap)  # return 2
heap  # [2, 7, 8, 23, 42, 37, 18, 23]

优先队列 Priority Queue

优先队列的特点：

• 给定一个优先级 Priority
• 每次 pop 操作都会返回一个拥有最高优先级的项

使用 heap 构建 Priority Queue:

import heapq
class PriorityQueue(object):
    def __init__(self): 
        self._queue = []  # 创建一个空列表用于存放队列
        self._index = 0  # 指针用于记录push的次序

    def push(self, item, priority):
        """队列由（priority, index, item)形式的元祖构成"""
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]  # 返回拥有最高优先级的项


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

    def __repe__(self):
        self.name = name

if __name__ == '__main__':
    q = PriorityQueue()
    q.push(Item('foo'), 5)
    q.push(Item('bar'), 1)
    q.push(Item('spam'), 3)
    q.push(Item('grok'), 1)
    for i in range(4):
        print(q._queue)
        print(q.pop())

对队列进行4次pop()操作，打印结果如下：

[(-5, 0, Item: 'foo'), (-1, 1, Item: 'bar'), (-3, 2, Item: 'spam'), (-1, 3, Item: 'grok')]
Item: 'foo'
[(-3, 2, Item: 'spam'), (-1, 1, Item: 'bar'), (-1, 3, Item: 'grok')]
Item: 'spam'
[(-1, 1, Item: 'bar'), (-1, 3, Item: 'grok')]
Item: 'bar'
[(-1, 3, Item: 'grok')]
Item: 'grok'

可以看到 pop() 是如何返回一个拥有最高优先级的项。对于拥有相同优先级的项（bar和grok），会按照被插入队列的顺序来返回。代码的核心是利用 heapq module。heapq.heappop() 会返回最小值项，因此需要把 priority 的值变为负，才能让队列将每一项按从高到低优先级的顺序来排序。