本章重点关注的是一种特殊的数据结构——堆。这种结构在数据结构课和算法课中多有介绍(其实本章内容与《算法导论》中第6章的内容“堆排序”比较相似)。本章介绍了堆以及其两种用途——优先级队列和排序。
<li><strong>堆数据结构</strong></li>
堆有两个特定的性质。一是顺序,即任何结点的值都小于或等于其子结点的值,这意味着根结点的值最小。二是形状,一般用一棵二叉树来表示堆,树是平衡的,它最多在两层上具有叶结点,其中最底层的叶结点尽可能地靠左分布。因此,如果堆有n个结点,那么所有结点到根结点的距离都不超过lgn。
因为堆是具有形状性质的二叉树,所以用数组来表示堆就足够了。其中常见的函数定义为:
root = 1 //根结点 value(i) = x[i] //下标为i的值 leftchild(i) = 2*i //i的左孩子下标 rightchild(i) = 2*i+1 //右孩子 parent(i) = i/2 //i的父结点下标 null(i) = (i < 1) or (i > n) //判断i不在堆中的条件
<li><strong>堆的两个关键函数</strong></li>
这两个关键函数用于在数组的一端不再具备堆的性质时对其进行调整。
第一个函数是siftup,当我们将一个新的元素添加到数组的最后一个位置时,调用该函数将得到一个新的堆。
void siftup(n) pre n > 0 && heap(1, n-1) post heap (1, n) i = n loop /* invariant: heap(1, n) except perhaps between i and its parent */ if i == 1 break p = i / 2 if x[p] <= x[i] break swap(p, i) i = p
第二个函数是siftdown,当x[1..n]是一个堆时,给x[1]分配一个新值得到heap(2,n),然后用函数siftdown使得heap(1,n)为真。其实现原则是:将顺序不对的元素和比它小的子结点中较小的那个交换。
void siftdown(n) pre heap(2, n) && n >= 0 post heap(1, n) i = 1 loop /* invariant: heap(1, n) except perhaps between i and its (0, 1 or 2) children */ c = 2 * i if c > n break if c+1 <= n /* c+1 is the right child of i */ if x[c+1] < x[c] c++ if x[i] <= x[c] break swap(c, i) i = c
<li><strong>优先级队列</strong></li>
优先级队列操作一个初始为空的元素集合,称为S。insert函数在集合中插入一个新元素,函数extractmin删除集合中最小的元素,并通过单个参数t返回该值。
优先级队列的完整C++实现如下:
template<class T> class priqueue{ private: int n, maxsize; T *x; void swap(int i, int j) { T t = x[i]; x[i] = x[j]; x[j] = t; } public: priqueue(int m){ maxsize = m; x = new T[maxsize+1]; n = 0; } void insert(T t){ int i, p; x[++n] = t; for (i = n; i > 1 && x[p=i/2] > x[i]; i = p) swap(p, i); } T extractmin(){ int i, c; T t = x[1]; x[1] = x[n--]; for (i = 1; (c = 2*i) <= n; i = c) { if (c+1 <= n && x[c+1] < x[c]) c++; if (x[i] <= x[c]) break; swap(c, i); } return t; } };
<li><strong>堆排序算法</strong></li>
上述优先级队列为我们执行排序提供了一种思路——先依次插入到队列中,再依次从队列中删除。但是优先级队列需要额外n+1个字的存储空间。堆排序在这点上与之不同——堆排序在原先的数据上建立数据结构,不需要额外数据空间。
首先,假设我们已经修改了siftup和siftdown,使它们能够操作最大元素在顶部的堆(通过交换“>”和“<”符号就能做到这一点)。
堆排序算法是一个两阶段的过程:前n步将数组建立到堆中,后n步按降序提取元素并从右到左建立最终的有序序列。代码如下:
for i = [2, n] //建立堆 siftup(i) for (i = n; i >= 2; i--) //按序提取元素 swap(1, i) siftdown(i-1)
<li><strong>原理总结</strong></li>
高效性。 堆的形状性质保证了其中的所有结点和根结点之间的层数在lgn之内。树的平衡性又保证了函数siftup和siftdown较高的运行效率。堆排序通过在原先存储元素的数组中执行减少了空间开销。
正确性。 可以通过不变式证明本章中各种堆操作的正确性。
抽象性。 好的工程师能够分清某个组件做什么(用户看到的抽象功能)和如何做(黑盒实现)之间的差别。
过程抽象。 你可以在不知道排序函数实现细节的情况下用它来排序数组,即将排序视为单个操作。
抽象数据类型。 数据结构做什么是由它的方法和方法的规范给出的,而如何做则是由具体实现决定的。
<li><strong>习题部分</strong></li>
在一些常见的问题中,使用堆来实现往往能得到很好的效果。比如下面几个例子:
1.计算大型浮点数集合的和,简单地把较小的浮点数相加可能会丢失精度。一种较好的算法每次都把集合中最小的两个数相加,这可以通过采用堆数据结构来实现。
2.在存有10亿个数的文件中查找最大的100万个数。可以用一个百万元堆(最小的元素在顶部)来表示目前所看到的最大的100万个数。
3.将多个较小的有序文件合并为一个较大的有序文件时,可以用堆表示每个文件中的下一个元素,从而实现对有序文件的归并。迭代步骤从堆中选出最小的元素,并将其后继插入堆中。n个文件中下一个待输出的元素可以在O(lgn)时间内选出。