2.4 Priority Queues

API

优先队列最重要的元素就是删除最大元素和插入元素。
介绍基于二叉堆数据结构的一种优先队列的经典实现方法，用数组保存元素并按照一定的条件排序，以实现高效地（对数级别的）删除最大元素和插入元素操作。
有序：当一颗二叉树的每个结点都大于等于它的两个子节点时，它被称为堆有序。

二叉堆表示法

二叉堆是一组能够用堆有序的完全二叉树的元素，并在数组中按照层级存储（不使用数组的第一个位置）。
完全二叉树只用数组而不需要指针就可以表示。并且可以实现对数级别的插入元素和删除最大元素的操作。
一颗大小为N的完全二叉树的高度为lgN。

堆实现的比较和交换方法

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))//位置k的父结点位置为k/2
	{
		exch(k/2, k);
		k = k/2;
	}
}//由下至上的堆有序化（swim）

如果一个子结点比父节点大，就需要交换子结点和父结点，子结点的位置为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;
    }
}//由上至下的堆有序化（下沉）

如果某个结点小于其子结点，那么要将这个结点和子结点中较大的值来交换。位置为k的结点的子结点的位置为2k和2k+1。
对优先队列API的实现可以保证插入元素和删除最大元素这两个操作的用时和队列的大小仅成对数关系。

索引优先队列
可以将名为pq的IndexMinPQ类优先队列看成数组pq[0…N-1]中的一部分元素的代表。

索引优先队列用例
利用IndexMinPQ的代码Multiway解决了多向归并问题：它将多个有序的输入流归并成一个有序的输出流。

堆排序

两个阶段：

堆的构造阶段，将原始数组重新组织安排到一个堆中
下沉阶段，从堆中按递减顺序取出所有元素并得到排序结果

排序实现：

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--); //将a[1]和a[N]交换并修复堆
        sink(a, 1, N);
    }
}

Exercise

Prove that sink-based heap construction uses at most 2n compares and at most n exchanges.
Solution. It suffices to prove that sink-based heap construction uses fewer than n exchanges because the number of compares is at most twice the number of exchanges. For simplicity, assume that the binary heap is perfect (i.e., a binary tree in which every level is completed filled) and has height h.
Alternate heapify analysis

We define the height of a node in a tree to be the height of the subtree rooted at that node. A key at height k can be exchanged with at most k keys beneath it when it is sunk down. Since there are 2h−k nodes at height k, the total number of exchanges is at most:

Alternate heapify analysis
The first equality is for a nonstandard sum, but it is straightforward to verify that the formula holds via mathematical induction. The second equality holds because a perfect binary tree of height h has 2h+1 − 1 nodes.
Proving that the result holds when the binary tree is not perfect requires a bit more care. You can do so using the fact that the number of nodes at height k in a binary heap on n nodes is at most ceil(n / 2k+1).
Alternate solution. Again, for simplicity, assume that the binary heap is perfect (i.e., a binary tree in which every level is completed filled). We define the height of a node in a tree to be the height of the subtree rooted at that node.

First, observe that a binary heap on n nodes has n − 1 links (because each link is the parent of one node and every node has a parent link except the root).
Sinking a node of height k requires at most k exchanges.
We will charge k links to each node at height k, but not necessarily the links on the path taken when sinking the node. Instead, we charge the node the k links along the path from the node that goes left-right-right-right-…. For example, in the diagram below, the root node is charged the 4 red links; the blue node is charged the 3 blue links; and so forth.
Note that no link is charged to more than one node. (In fact, there are two links not charged to any node: the right link from the root and the parent link from the bottom rightmost node.)
Thus, the total number of exchanges is at most n. Since there are at most 2 compares per exchange, the number of compares is at most 2n.

设计一个程序，在线性时间内检测数组pq[]是否是一个面向最小元素的堆。

private boolean isMinHeap() {
        return isMinHeap(1);
    }
    // is subtree of pq[1..n] rooted at k a min heap?
private boolean isMinHeap(int k) {
        if (k > n) return true;
        int left = 2*k;
        int right = 2*k + 1
        if (left  <= n && greater(k, left))  return false;
        if (right <= n && greater(k, right)) return false;
        return isMinHeap(left) && isMinHeap(right);
    }

API

堆排序

Exercise

Creative Problems(N)