7-PriorityQueues

优先队列 PQ API 和基本实现

和队列 Quene 类似，不同的地方在于我们希望可以移除队列中的最大（最小）的元素。注意泛型元素必须满足 Comparable

基本实现

1. 无序数组，删除时遍历寻找最大
2. 有序数组，插入时完成排序
3. 目标，插入、删除的操作复杂度都是对数级别的

二叉堆 Binary Heap

• 二叉堆可以视为一个完全二叉树，父节点一定大于（或小于）它的两个子结点
• 实际可以表示成数组

增加元素

将元素增加到末尾，并进行上滤操作

上滤 swim ：不断和父节点比较直到找到合适的位置

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

/**
     * Adds a new key to this priority queue.
     *
     * @param  x the new key to add to this priority queue
     */
    public void insert(Key x) {

        // double size of array if necessary
        if (n == pq.length - 1) resize(2 * pq.length);

        // add x, and percolate it up to maintain heap invariant
        pq[++n] = x;
        swim(n);
        assert isMaxHeap();
    }

删除元素

将堆中第一个元素和最后一个元素交换，删除最后一个元素，然后对第一个元素进行下滤操作

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

/**
     * Removes and returns a largest key on this priority queue.
     *
     * @return a largest key on this priority queue
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key delMax() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key max = pq[1];
        exch(1, n--);
        sink(1);
        pq[n+1] = null;     // to avoid loitering and help with garbage collection
        if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
        assert isMaxHeap();
        return max;
    }

代码实现

public class MaxPQ < Key extends Comparable < Key >> {
    private Key[] pq;
    private int N;
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity + 1];
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public void insert(Key key)
    public Key delMax() { /* see previous code */ }
    private void swim(int k)
    private void sink(int k) { /* see previous code */ }
    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. 采用不可变元素，避免PQ中的元素发生改变而影响性质
2. 下溢时抛出异常；上溢时考虑使用可变长数组 resizing array
3. 最小堆和最大堆实现方法类似，仅需更改 less()为greater()以及实现greater()。这里就体现出抽象less()和compareTo()的优势了
4. PQ 还支持其他操作，比如删除任意一个元素或者是改变某个元素的优先级，使用sink()和swim()可轻松完成。

不可变元素的实现

1. 方法设置为final避免被修改
2. 实例变量为private final
3. 从已知数据创建对象时要把输入对象复制一份以避免数组在其他地方被更改
4. 实例方法同样不改变实例变量

堆排序 Heapsort

两步走：

1. 建立最大堆
2. 重复删除最大值

PS. 这里的 sink()方法多了两个参数，第一个是待排序数组，第三个是数组长度，第二个元素和上述一致，即要下滤的元素 index。使用第三个参数来限制下滤的范围，排除已经排序好的元素。

建立最大堆

for (int k = N/2; k >= 1; k--) {
    sink(a, k, N);
}

重复删除最大值

while (N > 1) {
    exch(a, 1, N--);
    sink(a, 1, N);
}

代码实现

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param pq the array to be sorted
     */
    public static void sort(Comparable[] pq) {
        int n = pq.length;

        // heapify phase
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);

        // sortdown phase
        int k = n;
        while (k > 1) {
            exch(pq, 1, k--);
            sink(pq, 1, k);
        }
    }

复杂度分析

• 建最大堆过程比较和交换次数小于$2N$次
• 堆排序过程比较和交换次数小于$2NlgN$次

特点

• 原地排序，不使用额外空间
• 最坏情况也是$NlogN$
• 不稳定
• 每次循环的操作较多，多于快排
• 数组取值跨度大，不能充分利用 Cache 。例如快排访存连续性较强，而堆排访存过于分散。

总结