请求证明：构建二叉堆的元素比较次数至多为2n-2

给定一个包含n个元素的数组H，需要证明执行BUILD-MAX-HEAP过程时，元素的比较次数至多为2n-2。

伪代码 #

BUILD-MAX-HEAP (A)
1 heap-size [A] <- length[A]
2 for i <- |Length[A]/2| downto 1
3 do MAX-HEAPIFY (A, i)

MAX-HEAPIFY (A, i)
1 l <- LEFT (i)
2 r <- RIGHT (i)
3 if l <= heap-size [A] and A[l] > A[i]
4    then largest <- l
5    else largest <- i
6 if r <= heap-size [A] and A[r] > A[largest]
7    then largest <- r
8 if largest ≠ i
9    then exchange A[i] with A[largest]
10   MAX-HEAPIFY (A, largest)

初始思路 #

• BUILD-MAX-HEAP从第⌊n/2⌋个元素开始倒序遍历，每个非叶子节点都会调用一次MAX-HEAPIFY
• 每次调用MAX-HEAPIFY最多会进行2次比较（分别和左、右孩子比较），若当前节点不是最大值，会递归向下调用MAX-HEAPIFY
• 叶子节点无需处理，不会触发任何比较
• 每个非叶子节点的比较次数取决于它需要下沉的层数（即节点的高度）

正式推导 #

我们可以通过二叉堆的层数分布来计算总比较次数：

1. 二叉堆的节点分层定义
   设二叉堆的高度为h（叶子节点高度为0），对于一个包含n个节点的完全二叉树：

   • 第k层（从0开始计数，叶子为第0层）的节点数最多为2^k
   • 高度为k的节点，在MAX-HEAPIFY中最多需要下沉k次，每次下沉最多产生2次比较

2. 总比较次数的表达式
   总比较次数等于所有非叶子节点的比较次数之和，即：
   $$\text{总比较次数} \leq 2 \times \sum_{k=1}^h k \times \text{高度为k的节点数}$$
   这里乘以2是因为每次下沉操作最多触发2次比较。

3. 求和式的上限化简
   对于完全二叉树，所有节点的高度之和满足：
   $$\sum_{k=1}^h k \times \text{高度为k的节点数} \leq n - 1$$
   这个结论可以通过小例子验证：n=1时无是非叶子节点，和为0=1-1；n=2时仅1个高度为1的节点，和为1=2-1；n=4时高度为2的节点1个、高度为1的节点2个，和为2+1×2=4=4-0？不对，应该是4-1=3？哦，n=4时总节点数4，非叶子节点是前2个，根节点高度2，左孩子高度1，右孩子是叶子，所以高度之和是2+1=3=4-1，确实符合。更大的n也遵循这个规律：所有节点的高度之和不超过n-1。

4. 最终结论
   将求和式的上限代入总比较次数的不等式：
   $$\text{总比较次数} \leq 2 \times (n - 1) = 2n - 2$$

补充说明 #

• 当二叉堆是满二叉树时，总比较次数会接近2n-2，这是最坏情况
• 只有当节点需要下沉时才会触发递归，每次递归最多带来2次比较，因此每个高度为k的节点最多贡献2k次比较，求和后得到的上限就是2n-2

内容的提问来源于stack exchange，提问作者Lior