2018-03-09

Algs4笔记（五） --- 堆、优先队列与堆排序

我们知道，队列是一种FIFO的线性表，只允许在后端进行插入操作，在前端进行删除操作。由名字可看出，优先队列(Priority queue)的特殊之处就在“优先”二字，支持优先处理优先级高的元素，这样的元素通常是最大的或者是最小的。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务，优先级相同的元素按照其在优先队列中的顺序得到服务。

堆

优先队列的使用与队列类似，但若也类似地使用数组或链表实现，则无法支持高效的操作，我们选择堆(Heap)来实现优先队列。

在计算机科学中，堆是满足堆属性的一种专门基于树的数据结构，堆通常是一个可以被看做一棵树的数组对象。
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。
堆有序是指一棵二叉树的每个结点都大于等于它的两个子结点。
在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层所有的结点都连续集中在最左边，则此二叉树为完全二叉树。

在一个堆中，位置为\(k\)的结点的父结点的位置为\(k/2\)，两个子结点的位置分别为\(2k\)或\(2k+1\)。二叉堆有两个基本操作来维护堆的有序，分别是上浮swim()和下沉sink()。

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

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;
    }
}

优先队列

我们这实现的优先队列支持两种操作：删除最大的元素和插入元素。有了堆的帮助，我们可以高效地支持这两个操作，并且经过堆的抽象后，代码也很简洁。

public void insert(Key v) {
    pq[++N] = v;
    swim(N);
}

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

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

堆排序

我们将要排序的元素都插入到一个优先队列，然后不断重复删除最小的元素，这样就得到了一个有序的序列，这就是堆排序(Heap sort)的关键思想。堆排序分为两个阶段，堆的构造阶段和下沉排序阶段。在堆的构造阶段，我们将原始数组重新组织安排进一个堆中;在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。

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

    private static void sink(Comparable[] a, int n, int k) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(a, j, j+1))
                j++;
            if (!less(a, k, j)) break;
            exch(a, k, j);
            k = j;
        }
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i-1];
        a[i-1] = a[j-1];
        a[j-1] = t;
    }

    private static boolean less(Comparable[] a, int i, int j) {
        return a[i-1].compareTo(a[j-1]) < 0;
    }
    // ... ...
}

在上面的实现中，我们未对优先队列的具体表示隐藏，将要排序的数组本身作为堆，如此一来排序就无需额外空间。sort()方法中有两个循环，一个构造堆，一个下沉排序。在构造堆的过程中，我们选择了从右至左构造，这样可以减少一半的计算量。另外，此处的sort()方法和less()方法和前面排序算法的通用辅助函数不同，因为堆不使用数组的第一位置，此处的两个方法都对索引减一，实现了从\(1\)为底到以\(0\)为底的一一映射。
将\(N\)个元素排序，堆排序只需少于\(2NlgN+2N\)次比较以及一半次数的交换。堆排序是现今我们所知的唯一能够同时最优地利用空间和时间的排序算法，即便是最坏的情况下也如此。堆排序代码短小，适合用来嵌入式开发，但在现代系统的应用中很少使用它，因为它很少和相邻的其他元素进行比较，无法利用系统的缓存。

堆

优先队列

堆排序

参考资料