2.4.20

问题：

Prove that sink-based heap construction uses fewer than 2N compares and fewer than N exchanges.

证明基于下沉方法建立堆使用少于2N次的比较和N次交换。

分析：

官方网站解答：https://algs4.cs.princeton.edu/24pq/

假设为堆是完美的。

我们将树中节点的高度定义为以该节点为根的子树的高度。

一个高度为k的节点，下沉最多交换k次，对于每一层，有：

$$ \begin{eqnarray} h + 2(h-1) + 4(h-2) + 8(h-3) + \ldots + 2^h (0) & = & 2^{h+1} - h - 2 \
& = & n - (h+1) \
& \le & n \end{eqnarray} $$

第一项使用等比数列求和公式，第二项错位相减法。

参考：

沈星繁