算法导论（六）－－堆排序

堆是一个数据结构，它是一棵完全二叉树。（完全树除最后一层外每层都是 填满的，而最后一层从左往右开始填直至到最后一个结点。）在这棵完全树中，每个父结点的值都不小于它的两个子结点的值（最大堆，也叫大根堆。如果小根堆则 每个父结点的值不小于它的两个子结点）。通常我们用数组表示堆，并用一个数值heapSize来表示数组最前面heapSize个元素构成了一个堆：

对于数组A，A[1]是堆的根。对于某个下标为i的结点，它的父结点、左儿子和右儿子的下标都可以简单计算出来：

PARENT(i) {
    return floor(i/2);
}

LEFT(i) {
    return 2*i;
}

RIGHT(i) {
    return 2*i + 1;
}

保持堆的性质

有时一个结点的左子树和右子树都是堆，但该结点本身却小于它的某个子结点，于是违反了堆的性质。我们可以通过下面的过程来使它变为一个堆：把违反堆性质的结点与值更大的子结点交换，再递归保持交换后的产生的新子树的堆性质。

相应的保持堆的伪代码：

MAX_HEAPIFY(A, i) {
1      l = LEFT(i);
2         r = RIGHT(i);
3         if l ≤ A.heaSize and A[l] > A[i]
4                  largest = l;
5         else
6                  largest = i;
7         if r ≤ A.heapSize and A[r] > A[largest]
8                  largest = r;
9         if largest ≠ i {
10                swap(A[i], A[largest]);
11                MAX_HEAPIFY(A, largest);
12    }
}

MAX_HEAPIFY的效率分析：一棵有n个元素，根结点为i的堆，其中每次交换父结点与子结点的开销为Ө(1)。它子树大小至多为2/3*n（在最坏情况发生在最底层恰好半满的时候），所以它的运行时间可以表示为：
T(n) ≤ T(2*n/3) + Ө(1)
根据主方法条件２可以得到T(n) = O(lg(n))。换而言之，保持堆的运行时间为O(lg(n))，或者说保持高度为h的堆的运行时间为O(h)。

建堆

对于一个数组A[1...n]，我们可把它看成一个违反堆性质的完全二叉树。在建堆时，从最下层的子树开始，使用前面所述的保持堆的算法，使得所有的子树都是一个堆，直至整棵二叉树A[1...n]就成为一个堆。
建（最大）堆的伪代码如下：

BUILD_MAX_HEAP(A) {
1        A.heapSize = A.length;
2        for i = floor(A.length/2) downto 1
3                MAX_HEAPIFY(A, i);
}

这个算法直观上看上去的运行时间为O(n*lg(n))，因为MAX_HEAPIFY的运行时间为O(lg(n))，而且MAX_HEAPIFY运行了O(n)次。但是这个上界不够紧确，下面更深入地分析建堆的效率：
一个元素数量为n的堆高度为floor(lg(n))，同时对于任意高度为h的子树，至多有ceiling(n/(2^(h+1)))个结点，而MAX_HEAPIFY作用在高度为h的结点上的时间为O(h)，所以总的建堆的运行时间可以表示为：
T(n) ≤ ∑ ceiling(n/(2^(h+1))) * O(h) = O(n*∑ h/2^h)
因为∑ h/2^h = 2 （等比数列求和），所以上式T(n) ≤ O(n*2) = O(n)。综上所述，建堆的运行时间为O(n)。

堆排序算法

在 基于数组A[1...n]建堆后，就可以用这个堆进行排序了。我们把数组A看成两部份，左侧为堆结构，右侧为排好序的序列。因为一个（最大）堆的根结点是 最大元素，所以我们每次把堆的根结点提取出来放入到数组A右侧的有序数列的最左边。每次提取根后，堆的大小减一，而右侧有序数列的大小加一。当整个堆都被 转移到有序数列的部分时，整个数组也就完成排序了。在每次转移堆的根结点时，需要用堆的最右元素来充当新的根，但这样可能会违反堆的性质，所以需要保持堆 的操作。下面是伪代码：

HEAPSORT(A) {
1      BUILD_MAX_HEAP(A);
2       for i = A.length downto 2 {
3              swap(A[1], A[i]);
4              A.heapSize = A.heapSize - 1;
5              MAX_HEAPIFY(A, 1);
6       }
}

堆排序算法的运行时间为O(n*lg(n))。

优先级队列

虽然堆排序算法很漂亮，但在实际中它往往比不上快速排序算法。仅管如此，堆数据结构仍然有很大的作用，比如实现优先级队列（priority queue）。与堆一样，优先级队列也有两种：最小优先级队列和最大优先级队列。

（最大）优先级队列每次取元素时都返回优先级最高的元素，它包含以下操作：
INSERT(S, x)：把元素x插入集合S。
MAXIMUM(S)：返回S中的最大元素。
EXTRACT_MAX(S)：去掉并返回S中的最大元素。
INCREASE_KEY(S, x, k)：将元素x的关键字的值增加到k，这里k值不能小于x的原关健字的值。

下面给出以上操作的伪代码：

HEAP_MAXIMUM(A) {
1     return A[1];
}

HEAP_MAXIMUM的运行时间为O(1)。

HEAP_EXTRACT_MAX(A) {
1      if A.heapSize < 1
2                  error("heap underflow");
3   max = A[1];
4         A[1] = A[A.heapSize];
5         A.heapSize = A.heapSize - 1;
6         MAX_HEAPIFY(A, 1);
7         return max;
}

HEAP_EXTRACT_MAX的运行时间为O(lg(n))，主要消耗在MAX_HEAPIFY的操作上。

HEAP_INCREASE_KEY(A, i, key) {
1      if key < A[i]
2                  error("new key is smaller than current key");
3   A[i]=key;
4      while i>1 and A[PARENT(i)]<A[i] {
5           swap(A[i], A[PARENT(i)]);
6           i = PARENT(i);
7      }
}

HEAP_INCREASE_KEY的运行时间为O(lg(n))，因为要执行lg(n)（堆的高度）次交换操作

MAX_HEAP_INSERT(A, key) {
1      A.heapSize = A.heapSize + 1;
2         A[A.heapSize] = -∞;
3         HEAP_INCREASE_KEY(A, A.heapSize, key);
}

MAX_HEAP_INSERT的运行时间为O(lg(n))，主要消耗在HEAP_INCREASE_KEY的操作上。