2.4 优先队列 Priority Queue

• 优先队列的数据结构支持两种操作：删除最大元素和插入元素
• 优先队列的使用和队列（删除最老的元素）以及栈（删除最新的元素）类似
• 通过插入一列元素然后一个个地删除其中最小的元素，可以用优先队列实现排序算法。一种

名为堆排序的重要排序算法也来自于基于堆的优先队列的实现

API

优先队列是一种抽象数据类型，他表示了一组值和对这些值得操作。优先队列最重要的操作就是删除最大元素和插入元素。

• 删除最大元素的方法名为 del_max()
• 插入元素的方法名为 insert()

（MinPQ，和MaxPQ类似，只是含有一个 del_min() 方法来删除并返回队列中健值最小的那个元素，只需要改变下 less() 比较的方向即可）

优先队列的应用场景

输入 N 个字符串，每个字符串都应着一个整数，任务就是找出最大的（或是最小的）M 个整数（以其关联的字符串）。在某些应用场景中，输入量可能非常巨大，甚至可以认为输入是无限的。

1. 一种方法是输入排序然后从中找出 M 个最大的元素。
2. 另一种方法是将每个新的输入和已知的 M 个最大元素比较，但除非 M 较小，否则这种比较的代价会非常高昂。

只要我们能够高效地实现 insert() 和 del_min()，调用了 MinPQ 的 TopM 就能使用优先队列解决这个问题。

构造一个用数字作为键的优先队列。当优先队列的大小超过 M 时就删掉其中最小的元素。处理完所有数据，有些队列中存放这一增序排列的最大的 M 个元素。

初级实现

可以使用无序（数组）或是有序（数组 / 链表）的方法来实现优先队列。
使用无需序列是解决这个问题的惰性方法，我们仅在必要的时候才会采取行动；使用有序序列则是解决问题的积极方法，因为我们会尽可能未雨绸缪，是后续操作更高效。

堆的定义

数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，在堆有序的二叉树中，每个结点都小于等于它的父结点。

当一颗二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

二叉堆表示法
完全二叉树只用数组而不需要指针就可以表示。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置 1，它的子结点在位置2，3，而子结点的子结点则分别在位置4，5，6，7...

二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。

在一个堆中，位置 k 的结点的父结点的位置为 [k/2]，而它的两个子结点的位置则分别为 2k，2k + 1。（这样在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动。）

堆的表示

用数组（堆）实现的完全二叉树的结构是很严格的，但它的灵活性已经足以让我们高效地实现优先队列。用它们我们将能实现对数级别的插入元素和删除最大元素的操作。利用在数组中无需指针即可沿树上下移动的便利和以下性质，算法保证了对数复杂度的性能。

一个大小为 N 的完全二叉树的高度为 [lgN]

堆的算法

用长度为 N+1 的数组 pq[] 来表示一个大小为 N 的堆，不使用 pq[0]，堆元素放在pq[1] 至 pq[N] 中。

堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。这个过程叫做堆的有序化 reheapifying。

在有序化的过程中，会遇到两种情况：

• 某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序
• 某个结点的优先级下降（例如，将根结点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序

由下至上的堆有序化 （上浮 swim）

如果堆的有序状态因为某个结点变得比它的父结点更大了而被打破，那么我们就需要通过交换它和它的父结点来修复堆。但这个结点仍然可能比它现在的父结点更大。我们可以不断地用同样的办法恢复秩序。（位置 k 的结点的父结点的位置是 [k // 2]）

private void swim(int k){
    while(k > 1 && less(k/2, k)){
        exch(k/2, k);
        k = k/2;
    }
}

    def swim(pq, k):
        while k > 1 and pq[int(k/2)] < pq[k]:
            pq[int(k/2)], pq[k] = pq[k], pq[int(k/2)]
            k = int(k / 2)

由下至上的堆有序化 （上浮 swim）

由上至下的堆有序化（下沉 sink）

如果堆的有序状态因为某个结点变得比它的两个子结点或其中之一更小而被打破，那么我们可以通过将它和它的两个子结点中的较大者交换来恢复堆。交换可能会在子结点处继续打破堆的有序状态，因此需要不断地用相同的方式将其修复，将结点向下移动直到它的子结点都比它更小或是到达了堆的底部。

private void sink(int k){
    while (2 * k <= N){
        int j = 2 * k;
        if(j < N && less(j, j+1)) j++;
        if(!less(k,j)) break;
        exch(k, j);
        k = j;
    }
}

def sink(pq, k):
    while(2 * k <= N):
        j = 2 * k
        if j < N and pq[j] < pq[j+1]: j+=1
        if !pq[k] < pq[j]: break
        pq[k], pq[j] = pq[j], pq[k]
        k = j

由上至下的堆有序化（下沉 sink）

sink() 和 swim() 方法是高效实现优先队列的基础。

插入元素
将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置.

删除最大元素
从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。

堆的操作

class MaxPQ():
    def __init__(self):
        self._pq = [None]
        self._index = 0

    def is_empty(self):
        return self._index == 0

    def size(self):
        return self._index

    def swim(self, k):
        while k > 1 and self._pq[k//2] < self._pq[k]:
            self._pq[k//2], self._pq[k] = self._pq[k], self._pq[k//2]
            k = k // 2

    def sink(self, k):
        while(2 * k <= self._index):
            j = 2 * k
            if j < self._index and self._pq[j] < self._pq[j+1]: 
                j+=1
            if self._pq[k] > self._pq[j]:
                break
            self._pq[k], self._pq[j] = self._pq[j], self._pq[k]
            k = j

    def insert(self, v):
        self._index += 1
        if len(self._pq) <= self._index:
            self._pq.append(None)
        self._pq[self._index] = v
        print(self._index)
        self.swim(self._index)

    def del_max(self):
        if self.is_empty():
            print("Priority Queue is empty")
            return
        max = self._pq[1]
        self._pq[1] = self._pq[self._index]
        del self._pq[-1]
        self._index -= 1
        self.sink(1)
        return max

    def show(self):
        return self._pq

优先队列由一个基于堆的完全二叉树表示，存储于数组 pq[1..self._index] 中，pq[0] 没有使用。在 insert() 中，将 self._index 加一，并把新元素添加到数组最后，然后用 swim() 恢复堆的秩序。在 del_max() 中，从 pq[1] 中得到需要返回的元素，然后将 pq[self._index] 移动到 pq[1]，并将 self._index 减一并用 sink() 恢复堆的秩序。同时还将不再使用的 pq[-1] 删除，以便系统回收它所占用的空间。

对于一个含有 N 个元素的基于堆的优先队列，插入元素操作只需不超过 （lgN + 1）次比较，删除最大元素的操作需要不超过 2lgN 次比较。

对于需要大量混杂的插入和删除最大元素操作的应用来说，命题意味着一个重要的性能突破。使用有序或是无序数组的优先队列的初级实现总是需要线性时间来完成起中一种操作，但基于堆的实现则能够保证在对数时间完成它们。

多叉堆

基于用数组表示的完全三叉树构造堆。对于数组中 1 至 N 的 N 个元素，位置 k 的结点大于等于位于 3k-1，3k，3k+1 的结点，小于等于位于 (k+1) // 3 的结点。

调整数组大小

对于静态语言来说，可以添加一个没有参数的构造函数，在 insert() 中添加将数组长度加倍的代码，在 del_max() 中添加将数组长度减半的代码。这样，算法的用例就无需关注各种队列大小的限制。

元素的不可变性

索引优先队列

做到这一点的一种简单方法是给每个元素一个索引。

class IndexMinPQ():

Function(Args)	Meaning
insert(k: int, item: Item) -> None	插入一个元素，将它和索引 k 相关联
change(k: int, item: Item) -> None	将索引为 k 的元素设为 item
contain(k: int) -> bool	是否存在索引为 k 的元素
delete(k: int) -> None	删去索引 k 及其相关联的元素
min() -> Item	返回最小元素
min_index() -> int	返回最小元素的索引
del_min() -> int	删除最小元素并返回它的索引
is_empty() -> bool
size() -> int

索引优先队列用例

调用了 IndexMinPQ 的代码 Multiway 解决了多项归并问题：它将多个有序的输入流归并成一个有序的输出流。

如果有足够的空间，你可以把他们简单地读入一个数组并排序，但如果用了优先队列，无论输入有多长都可以把他们全部读入并排序。

public class Multiway{
    public static void merge(In[] streams){
        int N = streams.length;
        IndexMinPQ<String> pq = new IndexMinPQ<String>(N);

        for(int i = 0; i < N; i++){
            if(!streams[i].isEmpty()){
                pq.insert(i, streams[i].readString());
            }
        }
        while (!pq.isEmpty){
            StdOut.println(pq.min());
            int i = pq.del_min();
            if(!streams.isEmpty()){
                pq.insert(i, streams[i].readString());
            }
        }
    }

    public static void main(String[] args) {
        int N = args.length();
        In[] streams = new In[N];
        for(int i = 0; i < N; i++){
            streams[i] = new In(args[i]);
        }
        merge(streams);
    }
}

class Multiway():
    def __init__(self):
        pass

    @classmethod
    def merge(cls, streams):
        # streams 是 file - objects, sorted 
        length = len(streams)
        pq = IndexMinPQ()
        # file in python cannot read file word by word
        # 这里按行来读
        for i in range(length):
            line = streams[i].readline().strip()  # strip() 把末尾的'\n'删掉
            if !line:
                pq.insert(i, line)

        while !pq.is_empty():
            print(pq.min())
            i = pq.del_min()
            line = streams[i].readline().strip()
            if !line:
                pq.insert(i, line)

def main(*args):
    streams = []
    for file in args:
        with open(file, mode='r') as f:
            streams.append(f)
    Multiway.merge(streams)


if __name__ == '__main__':
    main()

这段代码调用了 IndexMinPQ 来将作为命令行参数输入的多行有序字符串归并为一行有序的输出。每个输入流的索引都关联着一个元素（输入中的下一个字符串）。初始化之后，代码进入一个循环，删除并打印出队列中最小的字符串，然后将该输入的下一个字符串添加为一个元素。

堆排序

将所有元素插入一个查找最小元素的优先队列，然后在重复调用删除最小元素的操作来将他们按顺序删除。

堆排序可以分为两个阶段。在堆的构造阶段中，将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减顺序去除所有元素并得到排序结果。

堆的构造

更聪明高效的做法是从右至左用 sink() 函数构造子堆。数组的每个子位置都已知都一个子堆的根结点，sink() 对于这些子堆也适用。如果一个结点的两个子结点都已经是堆了，那么在该结点上调用 sink() 可以将它们变成一个堆。这个过程会递归地建立起堆的秩序。开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为 1 的子堆。

public static void sort(Comparable[] pq){
    int N = pq.length
    for(int k = N / 2; k >= 1; k--){
        sink(1, k, N);
    }
    while(N > 1){
        exch(pq, 1, N--)
        sink(pq, 1, N)
    }
}

def sort(pq):
    N = len(pq)
    for k in range(N / 2, 0, -1):
        sink(pq, k, N)
    while N > 1:
        pq[1], pq[N] = pq[N], pq[1]
        N -= 1
        sink(pq, 1, N) 

这段代码用 sink() 方法将 pq[1] 到 pq[N] 的元素排序。for 循环构造了堆，然后 while 循环将最大的元素 pq[1] 和 pq[N] 交换并修复了堆，如此重复直到堆变空。

堆排序：堆的构造（左）和下沉排序（右）

下沉排序

堆排序的主要工作都是在第二阶段完成的。这里将堆中的最大元素删除，然后放入堆缩小后数组中空出的位置。这个过程和选择排序有些类似，但所需的比较要少得多，因为堆提供了一种从未排序部分找到最大元素的有效方法。

将 N 个元素排序，堆排序只需少于（2NlgN + 2N ）此比较（以及一半次数的交换）。

先下沉后上浮

改进基于堆的优先队列的实现和堆排序的方法。

堆排序在排序复杂性的研究中有着重要的地位，因为它是我们所知的惟一能够同时最有地利用空间和时间的方法 -- 在最坏的情况下他也能保证使用 ～ 2NlgN 次比较和恒定的额外空间。当代码空间十分紧张的时候它很流行，因为它只用几行就能实现较好的性能。但现代系统的许多应用很少使用它，因为它无法利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中率要远远高于大多数比较都在相邻元素间进行的算法，如快速排序，归并排序，甚至是希尔排序。

另一方面，用堆实现的优先队列在现代应用程序中越来越重要，因为它能在插入操作和删除最大元素操作混合的动态场景中保证对数级别的运行时间。