题目

已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是()。

错因

A

只数了"12 与新位置的孩子比较一次"——只看了下沉的最后一步，漏了第一步要先在两孩子之间比一次、再与较小者比一次。下沉每层至少 2 次比较，第一步漏了。

B

数了下沉第一层的两次比较（兄弟比 1 次 + 与较小子比 1 次 = 2 次），但漏了第二层的比较：12 下沉到原 10 的位置后，还有一个孩子 16，必须再比一次。停得太早。

D

多算了一次比较。可能把"12 与左子 21 / 右子 16 都比"算成 2 次（实际只用 1 次比较找出较小子，因为只有 1 个孩子时根本不需要"兄弟比较"），或者多算了一步"12 与 21 比"——但下沉到原 10 位置时左右孩子只有 16 一个（21、34 是 15 的孩子，不是 12 的），不应该出现这一比。

总解析

初始小根堆（层序：8, 15, 10, 21, 34, 16, 12）：

删除堆顶 8：标准做法是把最后一个元素 12 移到根，再把 12 下沉到合适位置。删除后堆变为 6 个元素：12, 15, 10, 21, 34, 16。

下沉调整（每一层做 2 次比较：一次"两孩子比"找较小者，一次"父与较小子比"判断是否要交换）：

第一层（12 在根，索引 1）：

• 比较两孩子：15 vs 10 → 10 较小（第 1 次比较）
• 比较父与较小子：12 vs 10 → 12 > 10，交换（第 2 次比较）

调整后：

第二层（12 现在在原 10 的位置，索引 3）：

• 它只有一个孩子 16（无右子）→ 不需要兄弟比较，直接比父和这个孩子：12 vs 16 → 12 < 16，不换（第 3 次比较）

下沉结束。

总比较次数 = 1 + 1 + 1 = 3。

下沉比较计数公式：每"完整一层"算 2 次（兄弟比 + 父子比）；如果该层只有一个孩子（即下沉到只有左子的层），算 1 次（直接父子比）。

本题：第 1 层完整 2 个孩子 → 2 次；第 2 层只有 1 个孩子 → 1 次；之后没孩子 → 0 次。合计 3 次。

常见踩坑：很多人把"删除堆顶"想成"直接拿走根、左右子树合并"——其实是 "用最后一个元素填到根，再下沉调整"。下沉过程中的比较次数才是题目要的。

最终答案是 C（3）。