堆是一个数据结构,它是一棵完全二叉树。(完全树除最后一层外每层都是
填满的,而最后一层从左往右开始填直至到最后一个结点。)在这棵完全树中,每个父结点的值都不小于它的两个子结点的值(最大堆,也叫大根堆。如果小根堆则
每个父结点的值不小于它的两个子结点)。通常我们用数组表示堆,并用一个数值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)
根据主方法条件2可以得到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的操作上。
阅读(2121) | 评论(0) | 转发(7) |