本文讲述优先度列的五种实现方式，分别如下

  1. 无序数组
  2. 有序数组
  3. 链表
  4. 堆
  5. 二叉搜索树

然后分析一个问题。

优先队列是一种队列，它满足优先级别最高的先出队列。它的一个重要的应用时海量数据的排序，当我们需要找出10亿数据中的Top10项，不实际的解决方案是对所有数据排序，取Top10项。使用优先队列可以在很小的辅助空间内找出Top10项。具体思路如下：
（1）建立大小为k的容器
（2）每次从大数据集中读取一个数据项
（3）如果容器没有满，则把当前数据项加入容器
（4）如果容器已经满，找出容器中最小的元素（利用优先队列特性）如果当前数据项大于最小元素，则最小元素出队，当前数据项入队
（5）重复（2）到（3）直到读取完大数据集

上述的方案可以以并行的方式运行，最后合并结果。

无序数组的实现

无序数组实现方式的入队操作，直接把入队元素加到数组尾部。出队需要遍历数组，找出优先级别最高的出队，空缺的位置由后面元素依次补上。因此，入队的时间复杂度为O(1)，出队为O(N)。

有序数组的实现

由于要求数组有序，因此在插入的时候需要保存有序，插入操作需要找到适合的位置，然后在该位置插入，位置后面的元素依次往后移动，时间复杂度为O(n)。而出队，由于序列是有序，可以在O(1)内出队。

链表的实现

链表的实现和有序数组的实现原理上相似，不同的是队列元素采用链式存储结构。可以使用有序链表和无序链表。

上面三种实现思路由于有性能问题这里就不予实现。

使用堆实现

定义

堆：满足堆有序性质的树称为堆。堆有序指树的每个结点都大于等于它的孩子结点。特别地，如果树为二叉树，那么我们把满足堆有序的二叉树为二叉堆，简称为堆。

严格地，如果树的每个结点都大于等于它的孩子结点，称为最大堆，反之为最小堆。

在结构上，堆是完全二叉树。如果我们对堆的结点进行编号，从根结点起，从上到下，从左到有一次对结点编号为1,2,3…n。那么堆中的元素分别对应于数组A的A[1]、A[2]、…、A[n]（通常情况A[0]不存储元素），于是堆有两种存储方式：（1）使用链式结构，构造二叉树存放堆元素（2）使用数组，利用树的位置编号和数组位置索引一一对应。那么堆其拥有性质可以表达如下（以最大堆为例）：

1
2
3
N(k) > N(2k)
N(k) > N(2k+1)
N([k/2]) > N(k)

N(k)表示树的第k个结点或数组索引k位置元素的优先值。

操作

下面的操作一最大堆为例。

上浮

如果有一结点大于它的父结点，那么堆有序状态被打破了，需要把该结点和父结点交换，但这样也不能保证交换就满足堆有序。交换后的结点可能依然大于父结点，于是需要进一步交换。每一次的交换，如果堆有序还没有满足，就再次交换，就像该结点在不断上浮一样，直到堆的根结点结束。上浮的过程表达如下。

1
2
3
4
def swim(self, k):
    while k > 1 and self.less(k//2, k):
        self.exch(k//2, k)
        k = k // 2

下沉

类似于上浮，如果一个父结点（因外部操作）小于它的孩子结点，则需要下沉来维持堆有序。下沉操作是一个持续的过程直至满足堆有序。

1
2
3
4
5
6
7
8
9
def sink(self, k):
    while 2*k <= self.n:
        j = 2 * k
        if j < self.n and self.less(j, j+1):
            j += 1
        if not self.less(k, j):
            break
        self.exch(k, j)
        k = j

插入元素

优先队列的插入，在堆中的操作分为两部分：（1）把元素插入到数组尾部（2）从最尾部元素位置索引开始执行上浮操作。具体实现如下

1
2
3
4
def push(self, item):
    self._heap.append(item)
    self.n += 1
    self.swim(self.n)

弹出元素

在数组非空的情况下（不包括0位置元素），A[1]就是要弹出的元素，保存A[1]后，交换A[1]和A[n]，删掉A[n]后，从数组位置1开始执行下沉操作。具体实现如下

1
2
3
4
5
6
7
8
9
def pop(self):
    if self.empty():
        return None
    item = self._heap[1]
    self.exch(1, self.n)
    del self._heap[self.n]
    self.n -= 1
    self.sink(1)
    return item

实现

根据上面的讨论，基于堆的优先队列的完整实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class PriorityQueue:

    def __init__(self):
        array = [None]
        self._heap = array
        self.n = len(self._heap) - 1

    def __len__(self):
        return self.n

    def empty(self):
        return self.n == 0

    def exch(self, i, j):
        self._heap[i], self._heap[j] = self._heap[j], self._heap[i]

    def less(self, i, j):
        return self._heap[i] < self._heap[j]

    def swim(self, k):
        while k > 1 and self.less(k//2, k):
            self.exch(k//2, k)
            k = k // 2

    def sink(self, k):
        while 2*k <= self.n:
            j = 2 * k
            if j < self.n and self.less(j, j+1):
                j += 1
            if not self.less(k, j):
                break
            self.exch(k, j)
            k = j

    def push(self, item):
        self._heap.append(item)
        self.n += 1
        self.swim(self.n)

    def pop(self):
        if self.empty():
            return None
        item = self._heap[1]
        self.exch(1, self.n)
        del self._heap[self.n]
        self.n -= 1
        self.sink(1)
        return item

使用二叉搜索树实现

关于二叉搜索树的文章见二叉搜索树的原理、实现和应用，假定我们已经实现的BST，那么基于BST的优先队列的实现如下

1
2
3
4
5
6
7
8
9
10
class PriorityQueue(BinarySearchTree):

    def push(self, priority, item):
        self.insert(priority, item)

    def pop(self):
        _min = self.min()
        if _min:
            self.delete_min()
        return _min

使用BST实现的优先队列和堆实现的时间复杂度一样，入队、出队操作均为O(lgN)。

上面的五种实现中，都是线程不安全的，关系线程安全的实现见旧文线程安全的优先队列。

另外，根据堆构建的过程，我们不难写出堆排序算法。

1
2
3
4
5
6
7
8
9
def heapsort(list):
    length = len(list)
    k = length // 2
    for i in range(k, 0, -1):
        sink(list, i, length)
    while length > 1:
        exch(list, 1, length)
        length -= 1
        sink(list, 1, length)

一个问题？

最后，提出一个问题：使用栈实现优先队列，要求入队、出队时间复杂度为O(1)

完。

完。