优先队列

发表于 更新于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次就将它们排序。很多情况下我们会收集些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素，如此这般。例如，你可能有一台能够同时运行多个应用程序的电脑(或者手机)。这是通过为每个应用程序的事件分配一个优先级，并总是处理下一个优先级最高的事件来实现的。例如，绝大多数手机分配给来电的优先级都会比游戏程序的高。

在这种情况下，一个合适的数据结构应该支持两种操作: 删除最大元素和插入元素。这种数据类型叫做优先队列。优先队列的使用和队列（删除最老的元素）以及栈（删除最新的元素）类似，但高效地实现它则更有挑战性。

目录

API

泛型优先队列的API

初级实现

数组实现（无序）

数组实现（有序）

链表表示法

在一个优先队列上执行的一系列操作

堆的定义

数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推。如果我们将所有元素画成一棵二叉树，将每个较大元素和两个较小的元素用边连接就可以很容易看出这种结构。

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

相应地，在堆有序的二叉树中，每个结点都小于等于它的父结点(如果有的话)。从任意结点向上，我们都能得到一列非递减的元素;从任意结点向下，我们都能得到一列非递增的元素。 特别地:根结点是堆有序的二叉树中的最大结点。

二叉堆表示法

如果我们用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到它的上下结点（父结点和两个子结点各需要一个）。

一颗堆有序的完全二叉树

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

一棵大小为\(N\)的完全二叉树的高度为\([LgN]\)。

堆的表示

堆的算法

堆实现的比较和交换方法

1
2
3
4
5
6
7
8
9
private boolean less(int i, int j) {
    return pq[i].compareTo(pq[j]) < 0;
}

private void exch(int i, int j) {
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}

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

1
2
3
4
5
6
private void swin(int k) {
    while (k > 1 && less(k / 2, k)) {
        exch(k / 2, k);
        k = k / 2;
    }
}
由下至上的堆有序化（上浮）

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

1
2
3
4
5
6
7
8
9
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;
    }
}
由上至下的堆有序化（下沉）

基于堆的优先队列

堆的操作 
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
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;   //基于堆的完全二叉树
    private int n = 0;  //存储于pq[1..n]中，pq[0]没有使用

    public MaxPQ(int maxn) {
        pq = (Key[]) new Comparable[maxn + 1];
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public int size() {
        return n;
    }

    public void insert(Key v) {
        pq[++n] = v;
        swin(n);
    }

    public Key delMax() {
        Key max = pq[1];
        exch(1, n--);
        pq[n + 1] = null;
        sink(1);
        return max;
    }

    //辅助方法的实现见前
    private boolean less(int i, int j)
    private void exch(int i, int j)
    private void swin(int k)
    private void sink(int k)
}
由上至下的堆有序化（下沉）

多叉堆

调整数组大小

元素的不可变性

索引优先队列

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

索引优先队列用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Multiway {

    private 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.print(pq.minKey() + " ");
            int i = pq.delMin();
            if (!streams[i].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);
    }
}

堆排序

1
2
3
4
5
6
7
8
9
public static void sort(Comparable[] a){
    int n=a.length;
    for (int k=n/2;k>=1;k--)
        sink(a,k,n);
    while (n>1){
        exch(a,1,n--);
        sink(a,1,n);
    }
}

这段代码用sink()方法将a[1]到a[N]的元素排序(sink()被修改过，以a[]和N作为参数)。for循环构造了堆，然后while循环将最大的元素a[1]和a[N]交换并修复了堆，如此重复直到堆变空。将exch()和less()的实现中的索引减一即可得到和其他排序算法一致的实现(将a[0]至a[N-1]排序)。堆排序具体流程示意图显示在下图中。

堆排序的轨迹（每次下沉后数组内容）
堆排序：堆的构造（左）和下沉排序（右）

参考资料

《算法（第4版）》第二章排序2.3快速排序

本书网站