《编程珠玑》第 14 章──堆

本章使用堆主要解决排序和优先队列问题。

堆是用来表示元素集合的一种数据结构,其实就是一种完全二叉树。由于这种形状的二叉树可以很好的用数组来表示。

两个关键函数

对于堆的性质和堆排序的方法,我前面在 经典排序算法 就已经总结过了,这里就不再详细说明了。
堆排序主要就是两部分组成,先是 siftup 建堆,然后是 siftdown 调整堆。

优先级队列

其实就是内部维护着一个堆,在本文中,使用的是最小堆,也就是值最小的位于堆顶。插入新数的时候,把新树放到末尾,然后不断 siftup。取数的时候,把顶和最后一个交换一下,然后把原来是顶的数字取走,最后使用 siftdown 调整堆。

一种排序算法

参考 经典排序算法 中的堆排序即可。堆排序仅使用一个数组,因而可以节省空间。该算法使用了 n-1siftupn-1siftdown,每次操作的复杂度是 $O\left(\log n\right)$,所以总的时间复杂度是 $O\left(n\log n\right)$。

习题

1

实现基于堆的优先级队列,尽可能地提高运行速度。n 取何值时比顺序结构快?

和加快插入排序一样,减少移动时不断 swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
T extractmin() {
T t = x[1];
x[1] = x[n--];
int c, i;
int tmp = x[1];
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;
}
x[i] = x[c];
}
x[i] = tmp;
return t;
}

2

修改 siftdown 使之满足下列规范。

1
2
3
void siftdown(l,u)
pre heap(l+1,u)
post heap(l,u)

代码的运行时间是多少?说明如何用它来在 $O\left(n\right)$ 时间内构造一个 n 元堆,从而得到一个代码量更少且更快速的堆排序算法。

1
2
3
for (int i = n/2; i>=1; --i){
siftdown(i, n)
}

3

实现一个尽可能快的堆排序程序。你的程序与 11.3 节表格给出的排序算法相比性能如何?

1
2
3
4
5
6
7
for (int i = n/2; i >= 1; --i){
siftdown(i, n);
}
for (int i = n; i >= 2; --i){
swap(1, i);
siftdown(1, i-1);
}

4

如何使用优先级队列的堆实现解决下列问题?当输入有序时,你的答案有什么变化?

  1. 构建赫夫曼码(绝大多数关于信息理论的书和许多关于数据结构的书都会讨论这种编码)。
  2. 计算大型浮点数集合的和。
  3. 在存有 10亿 个数的文件中找出最大的 100万 个数。
  4. 将多个较小的有序文件归并为一个较大的有序文件(在实现1.3节那样的基于磁盘的归并排序程序时会出现这种问题)。

这些问题都是需要优先队列,每次取出两个最小的数字,然后相加合并后再插入到原来的队列中。

5

装箱问题需要将 n 个权值(每个都介于 0 和 1 之间)分配给最少数目的单位容量箱。解决这一问题的「首次适应」启发式方法按序考虑权值,将每个权值放到第一个合适的箱中(按升序扫描箱)。David Johnson 在他的 MIT 论文中指出,一种类似于堆的结构能够在 $O\left(n \log n\right)$ 时间内实现该启发式方法。说明如何实现。

把箱子的剩余空间做为值,进行建堆,比如建立一个小顶堆。那么从右往左,也就是从剩余空间由大到小来扫描,直到装不进去了,那么就可以找到能装下该物品的、剩余空间最小的箱子。把该物品装入进去,然后把这个点往上开始调整堆。这样的话,除非初始堆是单调递增的数组,如果还是用之前的方法建堆,那么找到的不一定是能装下该物品箱子中的剩余空间最小的箱子。

6

磁盘上顺序文件的常见实现让每个块都指向它的后继块,后继块可以是磁盘上的任意一个块。该方法要求写入一个块(因为文件已经写在硬盘上了)、读取文件的第一个块以及读完文件的第 i-1 个块后再读第 i 个块所需的时间都是同一个常数,从而从头开始读第 i 个块所需的时间跟 i 成正比。Ed McCreight 在施乐帕洛阿尔托研究中心设计磁盘控制器时发现,只要为每个结点增加一个额外的指针,就能获得其他所有的性质,但却使读取第 i 个块的时间正比于 $\log i$。如何实现这一点?解释一下这里读取第 i 个块的算法与习题 4.9 中在正比于 $\log i$ 的时间内计算 i 次幂的代码有什么共同点。

节点 i/2 指向节点 i,这样的话递归就可以在 $O\left(\log i\right)$ 的时间内找到节点 i。
4.9 题求 $x^n$ 也是用了类似的思想。

7

在一些计算机上,除以 2 以求出当前范围的中点是二分搜索程序中开销最大的部分。假设我们已经正确构建了待搜索的数组,说明如何使用乘以 2 的操作来替代除法。给出建立并搜索这样一个数组的算法。

这里要把堆看成树可能更好理解。把 x[1] 放二分点,x[2]x[3]放四分点。也就是小于 x[1] 就往左走,否则往右走。为了达到这样的树,初始数组肯定是先排好序的,然后复制到堆所对应的数组。放置的方法如下:模 2 余 1 的元素依次放入 b 的后半段,模 4 余 2 的元素放到 b 剩下的后半段,直到全部元素复制到 b 中。其实这里举个例子,在纸上画一边就很容易理解了。