从零开始的算法之路04——优先队列

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或是不一定要一次就将它们排序。很多情况下我们会收集一些元素，处理当前键值最大的元素，再收集更多的元素，如此循环。例如一台可以运行多个程序电脑，会给每个任务分优先级，并总是处理下一个优先级最高的事件。

在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫优先队列。

public class MaxPQ<Key extends Comparable<Key>> {
    // 创建一个优先队列
    public MaxPQ() {}

    // 创建一个初始容量为max的优先队列
    public MaxPQ(int max) {}

    // 用a[]中的元素创建一个优先队列
    public MaxPQ(Key[] a) {}

    // 向优先队列中插入一个元素
    public void insert(Key v) {}

    // 返回最大元素
    public Key max() {}

    // 删除并返回最大元素
    public Key delMax() {}

    // 返回队列是否为空
    public boolean isEmpty() {}

    // 返回优先队列中的元素个数
    public int size() {}
}

堆

数据结构二叉堆能够很好地实现优先队列地基本操作。在二叉堆的数组中，每个元素都要保证大于等于另外两个特定位置的元素。画成二叉树会很容易理解。

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

在堆有序地二叉树中，每个结点都小于等于它地父结点。从任意结点向上，我们都能得到一列非递减的元素。

根结点是堆有序的二叉树中最大的结点。

使用完全二叉树来表达堆有序的二叉树会非常方便，我们只需要用数组（而不需要额外记录父子关系的指针）就可以实现。

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

在一个（二叉）堆中，位置 k 的结点的父结点位置为 k/2 ，而它的两个子结点分别为 2k 和 2k+1。

辅助函数

我们依然使用 less() 和 exch() 分别来比较和交换元素，用长度为 N+1 的私有数组 pq[] 来表示大小为 N 的堆：

private Key[] pq;

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

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

如果堆有序状态因为某结点变得比它的父节点大而打破，那么我们就需要交换它和它的父节点来修复堆。

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

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

如果堆有序状态因为某结点变得比它两个子节点或是其中之一更小而被打破了，那么我们需要交换它和子节点中的较大者来恢复堆。

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

基本实现

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq; // 基于堆的完全二叉树
    private int N; // size

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

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

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

    // 创建一个优先队列
    public MaxPQ() {}

    // 创建一个初始容量为max的优先队列
    public MaxPQ(int max) {
        pq = (Key[]) new Comparable[max + 1];
    }

    // 用a[]中的元素创建一个优先队列
//    public MaxPQ(Key[] a) {}

    // 向优先队列中插入一个元素
    public void insert(Key v) {
        pq[++N] = v; // 尾部插入
        swim(N); // 上浮
    }

    // 返回最大元素
    public Key max() {
        return pq[1];
    }

    // 删除并返回最大元素
    public Key delMax() {
        Key v = pq[1];
        pq[1] =  pq[N]; // 从尾部取值替换根结点
        pq[N--] = null; // 将尾部置空
        sink(1); // 下沉根结点
        return v;
    }

    // 返回队列是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    // 返回优先队列中的元素个数
    public int size() {
        return N;
    }
}

堆排序

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列，然后重复调用删除最小元素的操作来将他们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次选择排序，而基于堆的优先队列这么做就是一种经典而优雅的排序算法——堆排序。

堆排序分两个阶段：先构造堆后删除元素排序。

构造堆我们可以跳过大小为1的子堆，因为它们并无子结点，他们占总数的一半。而对他们的父节点从下至上调用sink() 函数最终就能得到一个堆。

而排序阶段我们可以将根结点和末尾元素交换，长度减一，再将新的根结点下沉，如此重复即可有序。

这里要注意的是二叉堆数组是基1的，在 less 和 exch 函数中我们要将索引-1（将 a[0] 至 a[N-1] 排序）。

public class Heap {
    // 排序算法的实现
    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, N--, 1);
            sink(a, 1, N);
        }
    }

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

    // 比较前者是否小于后者
    private static boolean less(Comparable[] a, int i, int j) {
        i--; j--; // 构造二叉堆的数组是基1的，这里要减去（对a[0]至a[N-1]操作）
        return a[i].compareTo(a[j]) < 0;
    }

    // 交换数组中两个位置的元素
    private static void exch(Comparable[] a, int i, int j) {
        i--; j--; // 构造二叉堆的数组是基1的，这里要减去（对a[0]至a[N-1]操作）
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // 打印数组
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Comparable[] arr = {45, 2, 17, 0, 1, 85, 3, 51, 20};
        Heap.sort(arr);
        Heap.show(arr);
    }
}