Python面试题系列之17: 如何实现一个优先级队列？
Question
如何用Python实现一个按优先级排序的队列？并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素。
知识点详解
首先，我们需要知道什么是优先级队列？先从相关概念谈起。
队列，是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。
优先级队列的概念
在实际应用中却常常需要另一类队列，每次从队列中取出的是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。
特点
在优先级队列中每个元素都有一个优先权或值。当给每个元素分配一个数字来标记其优先级时，可设较小的数字具有较高的优先级，这样更方便地在一个集合中访问优先级最高的元素，并对其进行查找和删除操作。
对优先级队列，执行的操作主要有：查找，插入，删除。
- 在最小优先级队列(min Priority Queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素。
- 在最大优先级队列(max Priority Queue)中，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。
- 插入操作均只是简单地把一个新的元素加入到队列中。
- 当从优先级队列中删除一个元素时，可能出现多个元素具有相同的优先权。在这种情况下，把这些具有相同优先权的元素视为一个FIFO队列，按他们的入队顺序进行先后处理。
应用
优先队列最常见的用处便是基于优先队列实现的堆排序。利用优先队列找到、返回、删除最高优先级元素的快速性，将所有待排序的元素一个一个加入到优先队列中，然后依次返回优先级最高的元素，从而实现排序。
实现思路
为了实现优先队列，我们首先想到了链表。
采用链表的两种实现思路：
- 正常入队列，返回优先级最高的元素时采用遍历的方式；
- 入队列时进行排序，将优先级最高的排在队列头部，返回优先级最高的元素时只需返回头部元素即可。
但这两种实现方式的时间复杂度都较高。为了高效地实现优先队列，这里我们使用堆。
堆(Heap)，是利用完全二叉树的结构来维护数据的一种的数据结构，因此堆也叫做二叉堆。借助下面这张图可以直观的理解二叉堆的结构和特点：
观察上图我们不难发现，元素的标号n’与其父节点的标号n的关系为： 左节点n’ = 2n 、右节点n’ = 2n+1 ，这为我们递归的查找节点提供了路径。
正是因为堆这种二叉树的结构特性，一般利用堆进行一次查找的时间复杂度在O(1)~O(logN)之间，这也正是我们后面利用堆实现优先队列和堆排序降低算法的时间空间成本的原因。
类似于数据结构栈和队列的push和pop两个核心操作，堆的也有两个核心操作：上浮swim和下沉sink，它们是实现堆的有序化的基础，也是实现优先队列的基础。
堆化(heapify)，是将一个二叉树转化为一个堆数据结构的过程。在Python中我们可以使用内置模块heapq中的heapify(x)函数来实现将一个列表 x 转化为一个堆。
import heapq
x = [3, 4, 2, 6, 8, 8, 9, 5, 3]
heap = list(x)
heapq.heapify(heap)
heap
>>> [2, 3, 3, 4, 8, 8, 9, 5, 6]heap是被堆化后的列表，heap[0] = 2为最小项。
注意：此时heap的数据类型仍是一个list。
我们打印出heapq提供的方法
heapq.__all__
>>> ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']以heappop()为例，它会从堆列表中拿出并返回最小项。并且使堆保持不变（即heap[0]仍为最小项）。
heapq.heappop(heap)
>>> 2
heapq.heappop(heap)
>>> 3
heapq.heappop(heap)
>>> 3
heap
>>> [4, 5, 6, 9, 8, 8]我们在了解堆及其相关操作后，现在就用它来实现一个优先级队列，具体代码如下：
import heapq
class MyPriorityQueue:
def __init__(self):
# 创建一个空列表用于存放队列
self._queue = []
# 指针用于记录push的次序
self._index = 0
def push(self, priority, item):
"""队列由(-priority, index, item)形式的元祖构成"""
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
# 返回拥有最高优先级的项
return heapq.heappop(self._queue)[-1]在这里我们利用了heapq模块的heappush()方法和heappop()方法。其中heapq.heappush()在队列_queue上插入和删除第一个元素，并且队列_queue保证第一个元素拥有最高优先级。heappop()函数总是返回 “最小的” 的元素，这就是保证队列pop操作返回正确元素的关键。
在上面代码中，队列包含了一个(-priority, index, item)的元组。优先级为负，其目的是使得元素按照优先级从高到低排序。 这个跟普通的按优先级从低到高排序的堆排序恰巧相反。
而index变量的加入，是保证同等优先级元素的正确排序。通过保存一个不断增加的index下标变量，可以确保元素按照它们插入的顺序排序，而且index变量也在相同优先级元素比较的时候起到重要作用。
class Item(object):
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item: {!r}'.format(self.name)
q = MyPriorityQueue()
q.push(Item('Java'), 15.004)
q.push(Item('Python'), 8.350)
q.push(Item('C'), 13.300)
q.push(Item('C++'), 8.350)
q.push(Item('.NET'), 4.624)
for i in range(5):
print(q._queue)
[(-15.004, 0, Item: 'Java'), (-8.35, 1, Item: 'Python'), (-13.3, 2, Item: 'C'), (-8.35, 3, Item: 'C++'), (-4.624, 4, Item: '.NET')]我们现在对队列进行5次pop()操作
for i in range(5):
print(q.pop())
print(q._queue)打印结果如下：
Item: 'Java'
[(-13.3, 2, Item: 'C'), (-8.35, 1, Item: 'Python'), (-4.624, 4, Item: '.NET'), (-8.35, 3, Item: 'C++')]
Item: 'C'
[(-8.35, 1, Item: 'Python'), (-8.35, 3, Item: 'C++'), (-4.624, 4, Item: '.NET')]
Item: 'Python'
[(-8.35, 3, Item: 'C++'), (-4.624, 4, Item: '.NET')]
Item: 'C++'
[(-4.624, 4, Item: '.NET')]
Item: '.NET'
[]仔细观察可以发现我们通过pop()操作了返回优先级最高的元素。 另外如果遇到两个同优先级的元素（如这里的 C++和 Python），pop操作则会按照它们被插入到队列的顺序进行返回。
Answer
实现优先级队列，代码的核心是利用heapq模块，根据堆排序的特点heapq.heappop()会返回最小值项，因此需要把priority的值变为负，才能让队列将每一项按从最高到最低优先级的顺序级来排序。具体代码见上文。
后记
在Python中内置的heapq和queue分别给我们提供了堆和优先队列结构，但是queue.PriorityQueue实际上只是对heapq的简单封装，直接使用其 heappush / heappop 方法，所以很有必要了解heapq的用法。好了，以上就是本篇全部内容。
备注：本篇首发于知识星球「人人都是Pythonista」。
