题目

将关键字 6, 9, 1, 5, 8, 4, 7 依次插入到初始为空的大根堆 H 中，得到的 H 是（）。

错因

A

把"大根堆"和"全局降序数组"搞混。大根堆只要求每个父结点 ≥ 其两个孩子，并不要求层间或同层有序。A 选项 9, 8, 7, 6, 5, 4, 1 是降序排列，对应的二叉树同样满足堆性质，但与"按 6, 9, 1, 5, 8, 4, 7 顺序逐个插入"得到的具体结构不同——逐个插入只做必要的上浮交换，不会重排所有元素。

C

插入第 6 个元素 4 时漏做向上调整。前 5 步操作正确得到 [9, 8, 1, 5, 6]；第 6 步插入 4 到末尾位置 6，父结点（位置 3）是 1，4 > 1 必须上浮交换变为 [9, 8, 4, 5, 6, 1]。选 C 的人没做这次交换，留下 [9, 8, 1, 5, 6, 4]；接着插入 7（位置 7）时，父位置 3 是 1，7 与 1 交换得 [9, 8, 7, 5, 6, 4, 1] → 即选项 C。新插入的元素必须沿父亲链上浮，直到不大于父或到根。

D

多次漏做上浮。最早从插入 8 开始：插 8 到位置 5，父位置 2 是 6，8 > 6 应交换；选 D 没交换，停在 [9, 6, 1, 5, 8]。后续插入 4 也漏调整。整体只在"显然要换"的步骤才换，省略了"看似没问题"但实际不满足堆性质的步骤。每次插入后都必须老老实实从插入位置走到根，逐级比较。

总解析

插入操作：把新元素挂到完全二叉树的末尾位置，然后**沿父亲链上浮（与父交换）**直到不再大于父或到达根。下面用顺序数组表示堆（位置 i 的父在 ⌊i/2⌋，1-base）。

逐步模拟（"父→子" 的箭头表示发生了一次交换）：

步	插入	操作前数组	上浮过程	操作后数组
1	6	[ ]	—	[6]
2	9	[6]	9 在位置 2，父 6 < 9，交换	[9, 6]
3	1	[9, 6]	1 在位置 3，父 9 > 1，停	[9, 6, 1]
4	5	[9, 6, 1]	5 在位置 4，父 6 > 5，停	[9, 6, 1, 5]
5	8	[9, 6, 1, 5]	8 在位置 5，父 6 < 8，交换；上升到位置 2，父 9 > 8，停	[9, 8, 1, 5, 6]
6	4	[9, 8, 1, 5, 6]	4 在位置 6，父 1 < 4，交换；上升到位置 3，父 9 > 4，停	[9, 8, 4, 5, 6, 1]
7	7	[9, 8, 4, 5, 6, 1]	7 在位置 7，父 4 < 7，交换；上升到位置 3，父 9 > 7，停	[9, 8, 7, 5, 6, 1, 4]

最终堆（用二叉树呈现，验证大根堆性质）：

逐父检查：

• 9 ≥ 8 ✓，9 ≥ 7 ✓
• 8 ≥ 5 ✓，8 ≥ 6 ✓
• 7 ≥ 1 ✓，7 ≥ 4 ✓

层序数组表示：9, 8, 7, 5, 6, 1, 4。

最终答案是 B（9, 8, 7, 5, 6, 1, 4）。

关键操作要点：

• 大根堆 ≠ 完全降序数组，只要求父 ≥ 子。
• 每次插入到末尾位置后，必须沿父亲链上浮——哪怕看起来"已经是大根堆"，也要走一遍。
• 插入位置 的父亲在 （1-based），不要算错。