把 swap 函数中与临时变量相关的赋值移到循环之外，就可以使 siftdown 运行得更快。为使 siftup 运行得更快，除了可以这样做之外，还可以在 x[0] 中放一个哨兵元素，省去测试 if i == 1。
void siftdown(l, u)
pre heap(l+1, u)
post heap(l, u)
修改后的 siftdown 函数与本书的 siftdown 函数差别不大。赋值语句 i = 1 替换为了 i = l，与 n 的比较替换为了与 u 的比较。修改后函数的运行时间为 O(logu - logl)。下面的代码可以在 O(n) 时间内构造一个堆：
for (i = n-1; i >= 1; i--)
/* invariant:maxheap(i+1, n) */
siftdown(i, n)
/* maxheap(i, n) */
由于 maxheap(l, n) 对所有 l>n/2 的整数都为真，因此 for 循环的边界 n-1 可以改为 n/2。
for (i = n/2; i >= 1; i--)
siftdown(i, n)
for (i = n; i >= 2; i--)
swap(l, i)
siftdown(l, i-1)
其运行时间仍为 O(n log n) ，但是常系数比以前的堆排序要小一些。本书网站上的排序程序提供了几种堆排序实现。
堆实现使得下面 4 个问题中的 O(n) 过程变成了 O(log n) 过程。
构建赫夫曼码的迭代步骤选择集合中的两个最小结点，将其归并为一个新结点。这是通过两次 extractmin 调用和一次 insert 调用来实现的。如果输入的各频率是有序的，那么就可以在线性时间内计算出赫夫曼码，细节留做练习。
简单地把较小的浮点数和较大的浮点数相加可能会丢失精度。一种较好的算法每次都把集合中较小的两个数相加，类似于上面提到的构建赫夫曼码的算法。
用一个百万元堆（最小的元素在顶部）来表示目前所看到的最大的 100 万个数。
可以用堆来表示每个文件中的下一个元素，从而实现对有序文件的归并。迭代步骤从堆中选出最小的元素，并将其后继插入堆中。n 个文件中下一个待输出的元素可以在 O(log n) 时间内选出。
5. 装箱问题需要将 n 个权值（每个都介于 0 和 1 之间）分配给最少数目的单位容量箱。解决这一问题的“首次适应”启发式方法按序考虑权值，将每个权值放到第一个合适的箱中（按升序扫描箱）。David Johnson 在他的 MIT 论文中指出，一种类似于堆的结构能够在 O(n log n) 时间内实现该启发式方法。说明如何实现。
把箱序列组织成一种类似于堆的结构，堆的每个结点说明其后代中最不满的箱的剩余空间。在决定往哪里放新权值时，搜索尽可能地往左进行（只要左边最不满的箱有足够的空间放该权值），只有在迫不得已时才往右进行。这样所需的时间正比于堆的深度 O(log n)。当权值插入后，向上重新遍历该路径以调整堆中的权值。
6. 磁盘上顺序文件的常见实现让每个块都指向它的后继块，后继块可以是磁盘上的任意一个块。该方法要求写入一个块（因为文件已经写在硬盘上了）、读取文件的第一个块以及读完文件的第 i-1 个块后再读第 i 个块所需的时间都是同一个常数，从而从头开始读第 i 个块所需的时间跟 i 成正比。Ed McCreight 在施乐帕洛阿尔托研究中心设计磁盘控制器时发现，只要为每个结点增加一个额外的指针，就能获得其他所有的性质，但却使读取第 i 个块的时间正比于 log i。如何实现这一点？解释一下这里读取第 i 个块的算法与习题 4.9 中在正比于 log i 的时间内计算 i 次幂的代码有什么共同点。
堆具有结点 i 到结点 2i 的隐式指针，为磁盘文件也加上这一指针。
磁盘上顺序文件的常见实现使得块 i 指向块 i+1。Ed McCreight 发现，如果同时让结点 i 指向结点 2i，那么最多访存 O(log n) 次就能找到任意一个结点 n。下面的递归函数输出了访问的路径。
void path(n)
pre n >= 0
post path to n is printed
if n == 0
print "start at 0"
else if even(n)
path(n/2)
print "double to ", n
else
path(n-1)
print "increment to ", n
注意，这和习题 4.9 中在 O(log n) 时间内计算 xn 的程序是类似的。
x[0..6] 上的二分搜索使用了根为 x[3] 的隐式树。若使用 14.1 节的隐式树，情况会怎样？
修改后的二分搜索从 i = 1 开始，每次迭代将 i 设置为 2i 或 2i+1。元素 x[1] 包含中值，x[2] 包含第一个四分位值，x[3] 包含第三个四分位值，依此类推。S.R.Mahaney 和 J.I.Munro 发现了一种能在 O(n) 时间内将 n 元有序数组调整为“堆搜索”顺序的算法。作为该方法的先驱，考虑把一个 2k-1 元的有序数组 a 拷贝到一个“堆搜索”数组 b 中：a 中奇数位的元素按顺序放到 b 的后半部分，摸 4 余 2 位置的元素按顺序放到 b 中剩余部分的后半部分，依此类推。
对排序使用 O(n log n) 下界。如果 insert 和 extractmin 的运行时间都小于 O(log n)，那么排序时间可以小于 O(n log n)。说明如何使用这两个操作来更快地排序。
10. 体育爱好者都很熟悉堆的基本观点。假设在半决赛中，Brian 击败了 Al，Lynn 击败了 Peter，并且在决赛中 Lynn 战胜了 Brian，这些结果通常可绘制为：（图略）这样的“竞标赛树”在网球竞标赛和足球、棒球、篮球的季后赛中很常见。假设比赛的结果是一致的（在体育运动中这种假设通常是无效的），那么 2 号种子进入决赛的概率有多大？请根据运动员的赛前排名来安排比赛的场次。
C++ 标准模版库中支持堆的操作有 make_heap、push_heap、pop_heap 和 sort_heap 等。结合这些操作可以得到像下面这样简单的堆排序：
make_heap(a, a+n);
sort_heap(a, a+n);
标准模版库也提供了 priority_queue 支持。