目标

• 独立辨析堆中的核心概念、结构性质与算法关系；
• 对选择题写出排除干扰项的依据，而不只记忆答案字母；
• 对本组已有的综合题完成推导、算法设计或复杂度分析。

前置知识

建议先阅读5.2 堆与优先队列，再开始本组练习。

环境、输入与预期输出

• 环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
• 输入：13 道四选一选择题，3 道综合题。
• 预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。

作答方法

1. 选择题先独立判断并记录依据，再点击“提交答案”；
2. 提交后核对正确答案和解析，做错的题使用“重新作答”；
3. 综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
4. 对易混概念主动构造反例，说明条件变化后结论是否仍成立。

选择题

答题进度已答 0/13正确 0

第 1 题

难度★★★考点堆、大根堆、建堆、筛选法、自底向上

对关键字序列 12, 28, 35, 19, 14, 51 用 筛选法（自底向上 sift-down） 建大根堆，建堆完成后堆数组按层序输出（下标 1 到 6）是( )。

请选择一个答案

A51, 28, 35, 19, 14, 12

B51, 19, 35, 12, 14, 28

C51, 35, 28, 19, 14, 12

D51, 14, 35, 19, 28, 12

第 2 题

难度★★考点堆、大根堆、堆性质、数组判定

下列以数组（下标从 1 开始）表示的完全二叉树中，不是大根堆的是( )。

请选择一个答案

A[50, 30, 40, 20, 35, 10]

B[50, 40, 30, 20, 10, 25]

C[50, 35, 40, 30, 20, 15]

D[50, 30, 40, 25, 20, 35]

第 3 题

难度★★考点堆、大根堆、插入、上浮调整、sift-up

向大根堆 [50, 30, 40, 20, 25, 35]（下标 1 到 6）中插入关键字 45。按标准的"末尾添加 + 向上调整（sift-up）"算法完成插入后，关键字 45 在堆数组中的下标是( )。

请选择一个答案

A1

B3

C5

D7

第 4 题

难度★★★考点堆、大根堆、删除堆顶、deleteMax、下沉调整

对大根堆 [60, 45, 50, 30, 40, 25, 35]（下标 1 到 7）执行一次删除堆顶（deleteMax）操作。按标准算法"末尾元素填到堆顶 + 向下调整（sift-down）"完成后，新堆数组按层序输出是( )。

请选择一个答案

A50, 45, 35, 30, 40, 25

B45, 40, 50, 30, 35, 25

C50, 45, 35, 30, 25, 40

D35, 45, 50, 30, 40, 25

第 5 题

难度★★★★考点堆、大根堆、堆性质、第二大元素、反证

设大根堆含 n（n ≥ 3）个互不相同的关键字。关于该堆中第二大关键字在堆数组中的位置，下列说法正确的是( )。

请选择一个答案

A第二大关键字一定是 a[2]（即根的左孩子）

B第二大关键字一定在 a[2] 或 a[3] 中（即根的两个孩子之一）

C第二大关键字可能出现在 a[1]、a[2] 或 a[3] 中的任何一个

D第二大关键字可能出现在除根 a[1] 之外的任意位置

第 6 题

难度★★★考点堆、大根堆、建堆、逐个插入、sift-up

对关键字序列 12, 28, 35, 19, 14, 51 用逐个插入建堆算法（每读入一个关键字就执行一次 sift-up）建大根堆，建堆完成后堆数组按层序输出（下标 1 到 6）是( )。

请选择一个答案

A51, 19, 35, 12, 14, 28

B51, 28, 35, 19, 14, 12

C51, 35, 28, 19, 14, 12

D35, 51, 28, 12, 14, 19

第 7 题

难度★★考点堆、大根堆、小根堆、双向堆、性质判定

下列数组（下标从 1 开始）描述完全二叉树形态。同时满足"既是大根堆又是小根堆"的是( )。

请选择一个答案

A[5, 5, 5, 5, 5]

B[10, 9, 8, 7, 6]

C[6, 7, 8, 9, 10]

D[10, 5, 10, 1, 5]

第 8 题

难度★★★考点堆、大根堆、时间复杂度、性能分析、操作对比

关于含 n 个关键字的大根堆，下列时间复杂度描述错误的是( )。

请选择一个答案

A用筛选法（自底向上）建堆的时间复杂度为 O(n)

B用逐个插入法建堆的时间复杂度为 O(n log n)

C删除堆顶元素（deleteMax）的时间复杂度为 O(log n)

D在堆中查找最大值的时间复杂度为 O(log n)

第 9 题

难度★★★★考点堆、大根堆、删除任意元素、末尾替代、向下调整、sift-down

从大根堆 [60, 55, 50, 45, 40, 25, 35]（下标 1 到 7）中删除关键字 55（位于 a[2]）。按标准的"用堆末尾元素替代被删位置 + 视情况上浮或向下调整（sift-down）"算法，调整完成后新堆数组（按层序）是( )。

请选择一个答案

A60, 45, 50, 35, 40, 25

B60, 35, 50, 45, 40, 25

C60, 40, 50, 45, 35, 25

D60, 45, 50, 25, 40, 35

第 10 题

难度★★★考点堆、小根堆、堆性质、数组判定、镜像练习

下列以数组（下标从 1 开始）表示的完全二叉树中，是小根堆的是( )。

请选择一个答案

A[3, 5, 4, 8, 7, 6]

B[3, 4, 5, 6, 7, 2]

C[3, 7, 4, 5, 8, 6]

D[5, 3, 4, 8, 7, 6]

第 11 题

难度★★★★★考点堆、大根堆、复合操作、插入、删除、多步推演

已知大根堆 [50, 30, 40, 20, 25, 35]（下标 1 到 6）。依次执行下列三步操作：

1. 插入关键字 45
2. 删除堆顶（deleteMax）
3. 插入关键字 50

三步全部完成后，堆数组按层序输出是( )。

请选择一个答案

A50, 30, 45, 20, 25, 35, 40

B45, 30, 40, 20, 25, 35

C50, 30, 40, 20, 25, 35, 45

D45, 30, 50, 20, 25, 35, 40

第 12 题

难度★★★考点堆、小根堆、建堆、筛选法、自底向上、镜像练习

对关键字序列 35, 28, 19, 51, 14, 12 用筛选法（自底向上 sift-down）建小根堆，建堆完成后堆数组按层序输出（下标 1 到 6）是( )。

请选择一个答案

A12, 14, 19, 51, 28, 35

B12, 14, 19, 28, 35, 51

C25, 40, 20, 35, 50, 12

D12, 19, 14, 51, 35, 28

第 13 题

难度★★★考点堆、小根堆、删除堆顶、deleteMin、sift-down、镜像练习

对小根堆 [10, 25, 20, 35, 40, 50]（下标 1 到 6）执行一次 deleteMin（删除堆顶最小值）。按标准算法"末尾元素填到堆顶 + 向下调整（sift-down）"完成后，新堆数组按层序输出是( )。

请选择一个答案

A20, 25, 50, 35, 40

B50, 25, 20, 35, 40

C25, 40, 20, 35, 50

D10, 25, 20, 35, 40

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：A
3. 第 3 题：B
4. 第 4 题：A
5. 第 5 题：B
6. 第 6 题：A
7. 第 7 题：A
8. 第 8 题：D
9. 第 9 题：A
10. 第 10 题：A
11. 第 11 题：A
12. 第 12 题：A
13. 第 13 题：A

综合题

综合题 1

难度：★★★ · 分值：10 分

考点：堆、大根堆、建堆、筛选法、sift-down、算法设计

给定长度为 $n$ 的整数数组 $a$，将其视为一棵完全二叉树的层序存储（下标从 1 开始）。请设计一个时间复杂度尽可能低、空间复杂度为 $O(1)$ 的算法，原地将该数组调整为一棵大根堆。

本组 heap 题统一约定：

• 堆数组下标从 1 开始，$a[1..n]$ 是堆数据，$a[0]$ 留空（系统已置 0，不要把数据放进 $a[0]$）
• 完全二叉树父子下标关系：$a[i]$ 的左孩子是 $a[2i]$、右孩子是 $a[2i+1]$、父是 $a[\lfloor i/2\rfloor ]$
• 大根堆性质：对每个内部结点 $i$，都有 $a[i]\ge a[2i]$ 且 $a[i]\ge a[2i+1]$（左右兄弟之间无大小约束）
• 建堆策略（筛选法）：从最后一个非叶子结点 $\lfloor n/2\rfloor$ 开始倒序到 $1$，对每个内部结点调用 sift-down
• sift-down 单步动作：①选出较大孩子（两个孩子时严格比较，平手时优先选左——本约定保证答案形态唯一）；②若较大孩子 $>$ 当前结点，则交换并使当前结点下沉一层，继续 sift-down；③否则停止

任务：

(1) 给出算法的基本设计思想。

(2) 采用 C 语言描述算法，关键之处给出注释。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

数据结构定义（C 语言，）：

/* a 指向长度为 n+1 的整型数组：a[0] 占位（不参与堆），a[1..n] 是堆数据 */

函数签名：

void buildMaxHeap(int *a, int n);

约束：

• $1\le n\le 10000$，$|a[i]|\le {10}^5$
• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$（不申请新数组，常数个辅助变量即可）
• 函数为 void，原地修改 $a[1..n]$
• 不允许使用 C++ STL（priority_queue 等），必须从底层 sift-down 写起

测试覆盖维度：测试用例除常规情况外还包含以下边界，错误 时建议逐个排查：

• $n=1$（最小情形，外层循环不执行，原数组即合法）
• $n=2$ 升序（首元小于唯一孩子，需要一次交换）
• $n=2$ 降序（首元大于唯一孩子，原状即满足）
• 不规则中规模 $n=15$（含正负、奇偶交错，sift-down 触发链式下沉）
• 全相同元素（平手分支大量触发，验证"严格大于才换"——若用 $\ge$ 会做无意义交换且形态错乱）
• 含负数 + 含 $0$（混合极值）
• 接近 $n_{max}$ 的大规模 $n=6000$（验证 $O(n)$ 算法在大输入下 通过；若误用 $O(n^2)$ 错误下沉将 超时）

参考答案与详细解析

详细解析

思路分析

解法 1（直觉解）：逐个插入建堆

把数组当成一个"逐渐生长"的堆：从空堆开始，依次把 $a[1],a[2],\dots ,a[n]$ 一个个"插入"到堆的末尾，每次插入后**上浮（sift-up）**到正确位置。

• 上浮单步：把当前结点与父结点比较，若大于父则交换、当前结点上升一层，重复直到不大于父或抵达根
• 时间复杂度：插入第 $k$ 个元素的上浮代价是 $O(\log k)$，总代价$$T(n)=\sum _{k=1}^{n}O(\log k)=O(n\log n)$$
• 空间复杂度：$O(1)$（原地，没新申请数组）

解法 2（更优）：自下而上 sift-down 建堆

观察一个关键事实：在一棵完全二叉树里，叶子本身已经是合法的子堆（一个结点没有违反堆性质的孩子）。所以建堆只需要"修内部结点"，且应当自下而上——先把每棵小子树修成合法大根堆，再修上一层。

具体地：

1. 找最后一个非叶子结点：完全二叉树下标 $1..n$，最后一个非叶子是 $\lfloor n/2\rfloor$（它的左孩子下标 $2\lfloor n/2\rfloor \le n$，确实是合法结点；而 $\lfloor n/2\rfloor +1$ 的左孩子下标 $>n$，必为叶子）
2. 倒序遍历 $i=\lfloor n/2\rfloor ,\lfloor n/2\rfloor -1,\dots ,1$：对每个内部结点执行 sift-down
3. sift-down：把当前结点沿"较大孩子"方向下沉，直到不小于左右孩子或抵达叶子

关键不变量：在 sift-down 结点 $i$ 之前，以 $i$ 的左右孩子为根的两棵子树已经是合法大根堆（数学归纳：叶子天然合法；倒序处理保证下层先于上层）。所以 sift-down 只需要"把 $i$ 这一个不合法的结点下沉到合适位置"，无需重新扫整棵子树。

两解法对比

维度	解法 1 逐个插入（sift-up）	解法 2 自下而上（sift-down）
时间复杂度	$O(n\log n)$	$O(n)$
空间复杂度	$O(1)$	$O(1)$
思维难度	直觉，从空堆开始增长	需要先承认"叶子本身合法"+ 自下而上的归纳
课程 默认含义	单纯插入操作	"建堆"二字默认指此法（即筛选法）

题面要求时间 $O(n)$，解法 1 不达标。下方参考实现给出解法 2。

为什么自下而上是 $O(n)$（反直觉证明）

很多学习者第一反应："每次 sift-down 最坏 $O(\log n)$，做 $n/2$ 次 sift-down，岂不就是 $O(n\log n)$？" —— 这是一个把"最坏"误用为"平均"导致的过估。

正确的分析方式：按高度分层求和。设结点高度为 $h$（叶子 $h=0$，根 $h=\lfloor {\log }_{2}n\rfloor$）。高度为 $h$ 的结点最坏 sift-down 代价是 $O(h)$，高度为 $h$ 的结点数至多 $\lceil n/2^{h+1}\rceil$ 个。总代价：

$$T(n)=\sum _{h=0}^{\lfloor {\log }_{2}n\rfloor }\lceil \frac{n}{2^{h+1}}\rceil \cdot h\le \frac{n}{2}\sum _{h=0}^{\mathrm{\infty }}\frac{h}{2^h}$$

利用恒等式 $\sum _{h=0}^{\mathrm{\infty }}h\cdot x^h={\displaystyle \frac{x}{(1-x{)}^2}}$（在 $x=1/2$ 处取值为 $2$），得

$$T(n)\le \frac{n}{2}\cdot 2=n$$

即 $T(n)=O(n)$。直觉上"每个结点都可能 sift-down 一段路"，但大多数结点是叶子或近叶子层（高度极小），只有 $O(1)$ 个结点真的从根级别下沉了 $\log n$ 步。这种"小高度结点多、大高度结点少"的几何衰减是 $O(n)$ 的本质。

参考实现（C）

/* sift-down：把 a[i] 沿"较大孩子"方向下沉，
 * 直到不小于左右孩子或抵达叶子。
 * 平手时（左 == 右）优先选左，保证形态确定。 */
static void siftDown(int *a, int n, int i) {
    while (1) {
        int left  = 2 * i;
        int right = 2 * i + 1;
        if (left > n) return;                    /* 已是叶子 */
        int bigger = left;
        if (right <= n && a[right] > a[left]) {  /* 严格大于才选右 */
            bigger = right;
        }
        if (a[i] >= a[bigger]) return;           /* 已满足大根堆 */
        int t = a[i]; a[i] = a[bigger]; a[bigger] = t;
        i = bigger;                              /* 继续在新位置下沉 */
    }
}

/* buildMaxHeap：自下而上对 i = n/2, n/2-1, ..., 1 依次 sift-down */
void buildMaxHeap(int *a, int n) {
    for (int i = n / 2; i >= 1; i--) {
        siftDown(a, n, i);
    }
}

关键点说明：

• 外层循环 i = n/2 .. 1 倒序：倒序保证 sift-down 结点 $i$ 时，其左右子树已经是合法大根堆——这就是上面提到的"关键不变量"。若改为正序 i = 1 .. n/2，sift-down 的子树前提失效，结果会错。
• left > n 是 sift-down 的终止条件：当一个结点连左孩子都没有，它就是叶子，没有继续下沉的方向。比写 i > n/2 更直接：sift-down 内部不需要再关心"当前结点是不是叶子"，由 left > n 兜底。
• a[right] > a[left] 严格大于：平手时（$a[\text{left}]=a[\text{right}]$）必须选左孩子，否则下面"全相同元素"测试会让数组反复无意义交换、最终形态因实现差异而漂移。本组 测试用例 的 .out 是按"严格大于才选右"生成的，写成 $\ge$ 会让平手案例 错误。
• a[i] >= a[bigger] 也是严格"已满足才停"：用 $\ge$（不是 $>$）保证"父子等值"时立即停止，避免无意义自交换。

复杂度证明

时间 $O(n)$：

按结点高度 $h$ 分层求和。设树高 $H=\lfloor {\log }_{2}n\rfloor$，高度 $h$ 的结点最多 $\lceil n/2^{h+1}\rceil$ 个，每个 sift-down 最坏代价 $h$：

$$T(n)=\sum _{h=0}^H\lceil \frac{n}{2^{h+1}}\rceil \cdot h\le \frac{n}{2}\sum _{h=0}^H\frac{h}{2^h}\le \frac{n}{2}\cdot \sum _{h=0}^{\mathrm{\infty }}\frac{h}{2^h}=\frac{n}{2}\cdot 2=n$$

代入 $n=10000$，sift-down 累计比较次数约 $\le 2n=2\times {10}^4$，远低于解法 1 的 $n\log n\approx 1.3\times {10}^5$。

空间 $O(1)$：

只用了循环变量 $i$、下标 $\text{left}/\text{right}/\text{bigger}$、临时交换变量 $t$ 共 5 个 int，与 $n$ 无关。siftDown 用 while 循环写而非递归，没有 $O(\log n)$ 的递归栈开销。

形式化地：辅助空间 $S(n)=5\cdot \text{sizeof(int)}=O(1)$。

易错点

本题是 课程 标准的"自下而上筛选法建大根堆"。算法的核心难点不在指针操作，而在于对算法属性的认知——为什么是 $O(n)$ 而不是 $O(n\log n)$、为什么是自下而上而不是自上而下、为什么平手时优先选左。

1. 盲区 A：「sift-up 与 sift-down 用错场景」 【算法层】

   学习者最常踩的坑：把"建堆"误以为"逐个插入"，写出 $O(n\log n)$ 的上浮版本，看似能过题但复杂度不达标——题面明文要求 $O(n)$。

   • 错误推演：从空堆开始，依次插入 $a[1],a[2],\dots ,a[n]$，每次插入到末尾后上浮到合适位置。每次上浮代价 $O(\log k)$，总代价 $\sum _{k=1}^n\log k=O(n\log n)$
   • 正解共识：建堆默认指 筛选法（sift-down），不是逐个插入（sift-up）。两者都能建出合法大根堆，但中间路径不同 → 最终堆形态也不同

2. 盲区 B：「sift-down 选孩子时只看左孩子，不比较右孩子」 【算法层】

   有学习者写法是「先看左孩子，若 $a[\text{left}]>a[i]$ 就跟左换；再看右孩子，若 $a[\text{right}]>a[i]$ 就跟右换」——这是两次独立比较而非"选较大孩子"。

   • 错误推演：$a=[1,5,9,\dots ]$，下标 1 是 1，左孩子 5、右孩子 9。错写法第一步比左：$5>1$ 交换 → $a=[5,1,9,\dots ]$；第二步比右：$9>5$ 交换 → $a=[9,1,5,\dots ]$。但 1 没有继续下沉（错写法只 sift 一层），$a[2]=1$ 还在那里，破坏了 $a[2]\ge a[4]$ 的约束（如果 $a[4]$ 存在且 $>1$）
   • 正解共识：sift-down 是"父和较大孩子作一次三方比较"——先比左右孩子选较大者，再让较大者与父比；交换后还要继续 sift-down（不止一层）

3. 盲区 C：「建堆 $O(n)$ 反直觉，写成 $O(n\log n)$ 的答案」 【元层-复杂度认知】

   即便算法实现完全正确，子问题 (3) 写复杂度证明时学习者很容易"凭直觉"得出 $O(n\log n)$：

   "每次 sift-down 最多下沉 $\log n$ 层，做 $n/2$ 次，所以是 $O(n\log n)$。"

   • 错误推演：这个论证是把每个结点都按"最坏 sift-down 代价"$\log n$ 估算，相当于假设所有结点都从根级别开始下沉——但实际上 $n/2$ 个叶子高度为 0（不做下沉）、$n/4$ 个倒数第二层高度为 1、… 最坏只有 1 个根高度 $\log n$
   • 正解共识：按高度分层求和 $\sum _h\lceil n/2^{h+1}\rceil \cdot h$，等比 + 几何幂级数收敛到 $O(n)$。本题"参考实现"段已写出完整推导

4. 盲区 D：「下标 0 起 vs 1 起的左右孩子公式错位」 【算法层】

   课程 教材主流约定"下标从 1 起"，父子公式是 $2i/2i+1/\lfloor i/2\rfloor$。但 C 语言数组天然 0 起，工程习惯也是 0 起；学生混用两套约定时公式错位 1：

   • 若数据从 $a[0]$ 开始存（0 起），父子公式应是 $2i+1/2i+2/\lfloor (i-1)/2\rfloor$，不是 $2i/2i+1$
   • 若数据从 $a[1]$ 开始存（1 起，本题约定），父子公式才是 $2i/2i+1/\lfloor i/2\rfloor$
   • 错误推演：学习者看本题约定"下标 1 起"，便把数据存到 $a[0..n-1]$，又用 $2i/2i+1$ 当公式——$a[0]$ 的左孩子按公式是 $a[0]$ 自身（死循环），右孩子是 $a[1]$（错位）；从 $a[1]$ 开始的话又把首元当成了哨兵
   • 正解共识：本题统一使用"1 起"约定，$a[0]$ 占位（值 0，不参与堆），数据真正放进 $a[1..n]$；学生不要自作主张转成 0 起

5. 盲区 E：「交换后忘了递归继续下沉」 【算法层】

   sift-down 的伪代码常被简写为「比较 + 交换」两步，省略了"继续在新位置下沉"的循环。学习者抄伪代码时容易丢掉最后一步：

   /* 错误的 sift-down：只下沉一层 */
   if (a[bigger] > a[i]) {
       swap(&a[i], &a[bigger]);   /* 换完就 return */
   }

   • 错误推演：$a[1..7]=[1,9,8,2,3,4,5]$。sift-down 结点 1：左 9、右 8，较大孩子是左 9，9 > 1 交换 → $a=[9,1,8,2,3,4,5]$。错写法直接返回，但 1 现在在下标 2，其孩子是 $a[4]=2,a[5]=3$，都比 1 大，仍违反堆性质！正确做法是继续 sift 直到 1 满足堆性质或抵达叶子
   • 正解共识：sift-down 必须循环（或递归）直到「当前结点 $\ge$ 较大孩子」或「抵达叶子」。参考实现里 while (1) { ... i = bigger; } 的循环正是为此

综合题 2

难度：★★★ · 分值：13 分

考点：堆、大根堆、建堆、堆排序、sift-down、演算

给定长度为 12 的整型数组：

$$a[1..12]=(4,1,3,2,16,9,10,14,8,7,5,12)$$

下标从 1 起，将其视为完全二叉树的层序存储。

请完成下列任务：

(1) 用自底向上的筛选法对 $a$ 建大根堆，给出建堆终态（用 binary-tree fence 或"下标 → 值"数组皆可）；并写出建堆过程的关键步骤——哪几个非叶子结点的 sift-down 引起了下沉、各下沉到哪——不必逐帧画出每次 sift-down 后的完整树。

(2) 在 (1) 得到的大根堆上执行堆排序：说明每轮"取堆顶 → 与末尾交换 → 堆长减 1 → 对新堆顶 sift-down"的机制，画出前 2~3 轮（如 Round 1、Round 2）sift-down 后剩余堆的形态以体现过程，其余各轮写出"当前最大送入已排序区"的结果即可，不必逐轮画完整树。

(3) 给出最终升序数组。

作答提示：本题是巩固训练，写出关键步骤（建堆终态 + 前几轮排序）与最终结果即可，无需把 16 帧中间树全部手画——与真实考试阅卷口径一致。下方解析给出的逐帧全表是供你对照学习的，不是作答的最低要求。

本组统一约定：

• 下标从 1 起：$a[1..n]$ 是堆数据，$a[0]$ 占位（不参与堆）
• 父子下标公式：$a[i]$ 的左孩子是 $a[2i]$、右孩子是 $a[2i+1]$、父是 $a[\lfloor i/2\rfloor ]$
• 大根堆性质：对每个内部结点 $i$，$a[i]\ge a[2i]$ 且 $a[i]\ge a[2i+1]$
• 建堆策略（筛选法）：从最后一个非叶子 $\lfloor n/2\rfloor$ 开始倒序到 1，对每个内部结点调用 sift-down
• sift-down 单步：①选较大孩子（两孩子时严格比较，平手优先选左）；②若较大孩子 $>$ 当前结点，则交换、当前结点下沉一层、继续 sift-down；③否则停止
• 堆排序：第 $k$ 轮 $(k=1,2,\dots ,n-1)$ 把 $a[1]$ 与 $a[n-k+1]$ 交换，已排序区扩到 $a[n-k+1..n]$，对剩余堆长 $n-k$ 的 $a[1]$ 做 sift-down

参考答案与详细解析

详细解析

思路分析（演算过程拆 Step）

建堆前的"找最后一个非叶子"

$n=12$，$\lfloor n/2\rfloor =6$ → 最后一个非叶子是下标 6。倒序遍历 i = 6, 5, 4, 3, 2, 1，对每个内部结点调用 sift-down。

初始堆形态

4(1(2(14, 8), 16(7, 5)), 3(9(12, _), 10))

下标与值对照表：

下标 $i$	1	2	3	4	5	6	7	8	9	10	11	12
值 $a[i]$	4	1	3	2	16	9	10	14	8	7	5	12

(1) 建堆逐次演算

Step 1: sift-down i = 6（a[6] = 9）

下标 6 只有左孩子下标 12（值 12，右孩子下标 13 越界）。

• 较大孩子 = 左 12（独子），$a[12]=12>a[6]=9$ → 交换 → $a[6]=12,a[12]=9$
• 下沉到 i = 12：2 × 12 = 24 > n = 12，叶子，停

后堆形态：

4(1(2(14, 8), 16(7, 5)), 3(12(9, _), 10))
highlight: 12

Step 2: sift-down i = 5（a[5] = 16）— 不引起交换

左孩子下标 10（值 7），右孩子下标 11（值 5）。较大 = 左 10。$a[5]=16\ge 7$ → 直接停，无变化。

（依约定不画新帧）

Step 3: sift-down i = 4（a[4] = 2）

左孩子 8（值 14），右孩子 9（值 8）。较大 = 左 8（14 > 8）。$a[4]=2<14$ → 交换 → $a[4]=14,a[8]=2$。下沉到 i = 8：2 × 8 = 16 > n，叶子，停。

后堆形态：

4(1(14(2, 8), 16(7, 5)), 3(12(9, _), 10))
highlight: 14

Step 4: sift-down i = 3（a[3] = 3）

• i = 3：左 6（值 12），右 7（值 10）。较大 = 左 6（12 > 10）。3 < 12 → 交换 → $a[3]=12,a[6]=3$。下沉到 i = 6。
• i = 6：左 12（值 9），无右。较大 = 左 12（独子）。3 < 9 → 交换 → $a[6]=9,a[12]=3$。下沉到 i = 12：叶子，停。

后堆形态：

4(1(14(2, 8), 16(7, 5)), 12(9(3, _), 10))
highlight: 12, 9

Step 5: sift-down i = 2（a[2] = 1）

• i = 2：左 4（值 14），右 5（值 16）。较大 = 右 5（16 > 14）。1 < 16 → 交换 → $a[2]=16,a[5]=1$。下沉到 i = 5。
• i = 5：左 10（值 7），右 11（值 5）。较大 = 左 10（7 > 5）。1 < 7 → 交换 → $a[5]=7,a[10]=1$。下沉到 i = 10：2 × 10 = 20 > n，叶子，停。

后堆形态：

4(16(14(2, 8), 7(1, 5)), 12(9(3, _), 10))
highlight: 16, 7

Step 6: sift-down i = 1（a[1] = 4）— 最终一层，最深下沉

• i = 1：左 2（值 16），右 3（值 12）。较大 = 左 2。4 < 16 → 交换 → $a[1]=16,a[2]=4$。下沉到 i = 2。
• i = 2：左 4（值 14），右 5（值 7）。较大 = 左 4。4 < 14 → 交换 → $a[2]=14,a[4]=4$。下沉到 i = 4。
• i = 4：左 8（值 2），右 9（值 8）。较大 = 右 9（8 > 2）。4 < 8 → 交换 → $a[4]=8,a[9]=4$。下沉到 i = 9：2 × 9 = 18 > n，叶子，停。

建堆终态（大根堆）：

16(14(8(2, 4), 7(1, 5)), 12(9(3, _), 10))
highlight: 16

下标 → 值表：

$i$	1	2	3	4	5	6	7	8	9	10	11	12
$a[i]$	16	14	12	8	7	9	10	2	4	1	5	3

关键数值二次验算（条 26）：对建堆终态逐父子对核验大根堆性质——

父	左	右	大根堆？
$a[1]=16$	$a[2]=14$	$a[3]=12$	16 ≥ 14、16 ≥ 12 ✓
$a[2]=14$	$a[4]=8$	$a[5]=7$	14 ≥ 8、14 ≥ 7 ✓
$a[3]=12$	$a[6]=9$	$a[7]=10$	12 ≥ 9、12 ≥ 10 ✓
$a[4]=8$	$a[8]=2$	$a[9]=4$	8 ≥ 2、8 ≥ 4 ✓
$a[5]=7$	$a[10]=1$	$a[11]=5$	7 ≥ 1、7 ≥ 5 ✓
$a[6]=9$	$a[12]=3$	—	9 ≥ 3 ✓

全部满足 ✓

(2) 堆排序逐轮演算

约定记号：用 | 分隔"剩余堆区"与"已排序区"；高亮当前堆顶。

Round 1：swap $a[1]\leftrightarrow a[12]$，n → 11，sift-down(1, n=11)

• swap → $a[1]=3,a[12]=16$
• sift-down(1, n=11)：i=1（值 3）→ 左 2(14)、右 3(12) → 较大=左 → 3<14 → swap → 下沉到 i=2；i=2（值 3）→ 左 4(8)、右 5(7) → 较大=左 → 3<8 → swap → 下沉到 i=4；i=4（值 3）→ 左 8(2)、右 9(4) → 较大=右 9（4 > 2）→ 3<4 → swap → 下沉到 i=9：叶子，停

剩余堆（$a[1..11]$）+ 已排序 $a[12]$：

14(8(4(2, 3), 7(1, 5)), 12(9, 10))
highlight: 14

已排序区：16

Round 2：swap $a[1]\leftrightarrow a[11]$，n → 10，sift-down(1, n=10)

• swap → $a[1]=5,a[11]=14$
• sift-down(1, n=10)：i=1（5）→ 左 2(8)、右 3(12) → 较大=右 → 5<12 → swap → 下沉到 i=3；i=3（5）→ 左 6(9)、右 7(10) → 较大=右 7 → 5<10 → swap → 下沉到 i=7：2×7=14>10，叶子，停

剩余堆 + 已排序：

12(8(4(2, 3), 7(1, _)), 10(9, 5))
highlight: 12

已排序区：14 16

Round 3：swap $a[1]\leftrightarrow a[10]$，n → 9，sift-down(1, n=9)

• swap → $a[1]=1,a[10]=12$
• sift-down(1, n=9)：i=1（1）→ 左 2(8)、右 3(10) → 较大=右 3 → 1<10 → swap → 下沉到 i=3；i=3（1）→ 左 6(9)、右 7(5) → 较大=左 6 → 1<9 → swap → 下沉到 i=6：2×6=12>9，叶子，停

剩余堆：

10(8(4(2, 3), 7), 9(1, 5))
highlight: 10

已排序区：12 14 16

Round 4：swap $a[1]\leftrightarrow a[9]$，n → 8，sift-down(1, n=8)

• swap → $a[1]=3,a[9]=10$
• sift-down(1, n=8)：i=1（3）→ 左 2(8)、右 3(9) → 较大=右 3 → 3<9 → swap → 下沉到 i=3；i=3（3）→ 左 6(1)、右 7(5) → 较大=右 7 → 3<5 → swap → 下沉到 i=7：2×7=14>8，叶子，停

剩余堆：

9(8(4(2, _), 7), 5(1, 3))
highlight: 9

已排序区：10 12 14 16

Round 5：swap $a[1]\leftrightarrow a[8]$，n → 7，sift-down(1, n=7)

• swap → $a[1]=2,a[8]=9$
• sift-down(1, n=7)：i=1（2）→ 左 2(8)、右 3(5) → 较大=左 → 2<8 → swap → 下沉到 i=2；i=2（2）→ 左 4(4)、右 5(7) → 较大=右 5 → 2<7 → swap → 下沉到 i=5：2×5=10>7，叶子，停

剩余堆：

8(7(4, 2), 5(1, 3))
highlight: 8

已排序区：9 10 12 14 16

Round 6：swap $a[1]\leftrightarrow a[7]$，n → 6，sift-down(1, n=6)

• swap → $a[1]=3,a[7]=8$
• sift-down(1, n=6)：i=1（3）→ 左 2(7)、右 3(5) → 较大=左 → 3<7 → swap → 下沉到 i=2；i=2（3）→ 左 4(4)、右 5(2) → 较大=左 4 → 3<4 → swap → 下沉到 i=4：2×4=8>6，叶子，停

剩余堆：

7(4(3, _), 5(1, 2))
highlight: 7

已排序区：8 9 10 12 14 16

Round 7：swap $a[1]\leftrightarrow a[6]$，n → 5，sift-down(1, n=5)

• swap → $a[1]=1,a[6]=7$
• sift-down(1, n=5)：i=1（1）→ 左 2(4)、右 3(5) → 较大=右 3 → 1<5 → swap → 下沉到 i=3：2×3=6>5，叶子，停

剩余堆：

5(4(3, _), 1(2, _))
highlight: 5

已排序区：7 8 9 10 12 14 16

Round 8：swap $a[1]\leftrightarrow a[5]$，n → 4，sift-down(1, n=4)

• swap → $a[1]=2,a[5]=5$
• sift-down(1, n=4)：i=1（2）→ 左 2(4)、右 3(1) → 较大=左 → 2<4 → swap → 下沉到 i=2；i=2（2）→ 左 4(3)、右 5 越界（n=4），独子=左 → 2<3 → swap → 下沉到 i=4：叶子，停

剩余堆：

4(3(2, _), 1)
highlight: 4

已排序区：5 7 8 9 10 12 14 16

Round 9：swap $a[1]\leftrightarrow a[4]$，n → 3，sift-down(1, n=3)

• swap → $a[1]=2,a[4]=4$
• sift-down(1, n=3)：i=1（2）→ 左 2(3)、右 3(1) → 较大=左 → 2<3 → swap → 下沉到 i=2：2×2=4>3，叶子，停

剩余堆：

3(2, 1)
highlight: 3

已排序区：4 5 7 8 9 10 12 14 16

Round 10：swap $a[1]\leftrightarrow a[3]$，n → 2，sift-down(1, n=2)

• swap → $a[1]=1,a[3]=3$
• sift-down(1, n=2)：i=1（1）→ 左 2(2)，右 3 越界（n=2），独子=左 → 1<2 → swap → 下沉到 i=2：叶子，停

剩余堆：

2(1, _)
highlight: 2

已排序区：3 4 5 7 8 9 10 12 14 16

Round 11：swap $a[1]\leftrightarrow a[2]$，n → 1，sift-down(1, n=1)

• swap → $a[1]=1,a[2]=2$
• sift-down(1, n=1)：i=1 左 2 越界（n=1），直接停

剩余堆：

1
highlight: 1

已排序区：2 3 4 5 7 8 9 10 12 14 16

Round 11 之后 n = 1，外层循环终止。

(3) 最终升序数组

$$\boxed{{\displaystyle a[1..12]=(1,2,3,4,5,7,8,9,10,12,14,16)}}$$

关键数值二次验算（条 26）：直接对原数组 $(4,1,3,2,16,9,10,14,8,7,5,12)$ 做升序快排得 $(1,2,3,4,5,7,8,9,10,12,14,16)$ ✓ 与堆排序结果一致。

易错点

1. 盲区 A：「堆顶取出后用末尾元素填顶」（算法层 / 数据结构本质认知）

   有同学把堆排序的"取堆顶 → 输出"机械记成"用 $a[n]$ 填堆顶"——其实等价说法应是"$a[1]$ 与 $a[n]$ 交换，n 减 1"。两种说法在最终升序数组上等价，但实现细节不同：填顶 = 一次写 + n 减 1（堆顶值被覆盖直接丢失，需先存到额外位置）；交换 = 三次写 + n 减 1（堆顶值落到 $a[n]$ 原地作为已排序区一员）。

   • 错误推演：若写"填顶"版本而不暂存堆顶值，每轮丢一个值，最终输出只剩 sift-down 过程产生的中间状态，数组完全乱掉。
   • 正解共识：堆排序的本质是 in-place 升序排序——堆顶最大值放到 $a[n]$ 作为已排序区一员，而不是写到独立的输出数组。交换写法天然保留所有元素位置，是 课程资料的主流模板。本盲区命名为「堆顶取出方向幻觉」，跨题与 前置练习 partition 的"挖坑填数 vs 交换"对偶——都源于"是否需要暂存"的细节。

2. 盲区 B：「sift-down 比较只比一个孩子」（算法层）

   学习者写 sift-down 时常常只比左孩子或只比右孩子，忘了先选两个孩子中的较大者再与父比。

   • 错误推演：建堆 Step 5 i=2（值 1）时，若只比左孩子 a[4]=14：1<14 → swap 后 $a[2]=14$；但实际更大的孩子是右 a[5]=16，本应换到 16 上去——右子树就少了一次正确的"上提 16"动作，堆顶最终不是 16 是 14（错），整棵堆都歪了。
   • 正解共识：sift-down 每一步必须做三方比较：①两个孩子先比、②较大者与父比、③若较大者 > 父则换

3. 盲区 C：「自底向上的层级遍历起点错算成 $n-1$ 或 $n/2-1$」（算法层）

   课程 教辅约定"下标 1 起"时最后一个非叶子是 $\lfloor n/2\rfloor$（本题是 6），有同学习惯 0-indexed 写法把起点写成 $n/2-1$（本题 = 5），或者把"非叶子"和"叶子"概念搞混写成 $n-1$（本题 = 11，相当于从最后一个元素开始 sift-down，绝大多数循环都对叶子做无意义比较）。

   • 错误推演：若起点 = $n-1=11$：sift-down 11（叶子，立即返回）、sift-down 10（叶子，立即返回）……到 sift-down 6 才开始真正工作——大量空转但仍能算对；不过若起点 = $n/2-1=5$（漏掉下标 6 的非叶子），sift-down 5、4、3、2、1 都做了但 i=6 的子树（含 a[12]=12 这个比父大的）从未被调整，建堆终态 a[6]=9 而 a[12]=12（违反），整棵堆错。
   • 正解共识：本组约定 1 起 → 最后一个非叶子下标 = $\lfloor n/2\rfloor$，倒序到 1

4. 盲区 D：「以为堆排序是稳定排序」（元层 - 数据结构本质认知）

   学习者背"堆排序时间 $O(n\log n)$、空间 $O(1)$"时，常顺手把"稳定性"也归到"$O(n\log n)$ 排序都稳定"——这是对"稳定性"概念的错认。

   • 错误推演：考虑 $a=[3a,3b,1]$（$3a,3b$ 表示同值不同来源以区分原始顺序）。建堆：i=1（3a）→ 左 a[2]=3b、右 a[3]=1，较大=左（按"严格大于才选右"，3b 与 3a 平手时选左 3b）→ a[1]=3a >= 3b（平手不换），但若实现把 ≥ 改为 >（用 a[i] > a[bigger] 才停），3a 与 3b 还是平手——也不换。建堆终态 $a=[3a,3b,1]$。开始堆排序：Round 1 swap a[1]↔a[3]：$a=[1,3b,|3a]$，sift-down(1, n=2)：1 < 3b → swap → $a=[3b,1,|3a]$；Round 2 swap a[1]↔a[2]：$a=[1,|3b,3a]$ → 3a 与 3b 在最终升序里相对位置反了（原 3a 在 3b 之前，结果 3b 在 3a 之前）。
   • 正解共识：堆排序不稳定——长跳交换让等值元素相对顺序乱掉

5. 盲区 E：「建堆 $O(n)$ 与堆排序 $O(n\log n)$ 是同一个数量级」（元层 - 复杂度认知）

   有同学看到"自下而上建堆 $O(n)$"就以为"堆排序整体也 $O(n)$"——其实只有"建堆阶段" $O(n)$，"排序阶段"是 $O(n\log n)$，整体 $O(n\log n)$。

   • 错误推演：堆排序由两阶段组成——
     • 建堆阶段：自下而上 sift-down，按高度分层求和得 $O(n)$
     • 排序阶段：执行 $n-1$ 轮"swap + sift-down(1)"，每次 sift-down 从根开始最坏 $O(\log n)$，合计 $(n-1)\cdot O(\log n)=O(n\log n)$
   • 正解共识：堆排序时间复杂度 $=O(n)+O(n\log n)=O(n\log n)$（被排序阶段主导）。本盲区命名为「两阶段复杂度叠加错」，与

最终答案

• (1) 建堆共触发 6 次 sift-down（i = 6、5、4、3、2、1），其中 5 次产生变化（i = 6、4、3、2、1），i = 5 不变化；建堆终态 $a=(16,14,12,8,7,9,10,2,4,1,5,3)$
• (2) 堆排序共 11 轮，每轮把当前堆顶送到已排序区末尾
• (3) 最终升序数组 $a[1..12]=(1,2,3,4,5,7,8,9,10,12,14,16)$

综合题 3

难度：★★★★ · 分值：13 分

考点：堆、Top-K、小根堆、优先队列、堆性质、算法设计

现有保存在数组 $a[0..n-1]$ 的 $n$ 个整数（$n$ 远大于 $k$），请找出其中最大的 $k$ 个数，并按升序输出。要求算法时间复杂度尽可能低。

本组 heap 题统一约定：

• 堆数组下标从 1 开始：$h[1..k]$ 是堆数据，$h[0]$ 占位（不参与堆）
• 父子下标公式：$h[i]$ 的左孩子 $h[2i]$、右孩子 $h[2i+1]$、父 $h[\lfloor i/2\rfloor ]$
• 小根堆性质（与 101 / 102 的大根堆对偶）：对每个内部结点 $i$，$h[i]\le h[2i]$ 且 $h[i]\le h[2i+1]$；堆顶 $h[1]$ 是堆中最小值
• sift-down 单步动作（小根堆版本）：①选较小孩子（两孩子时严格比较，平手优先选左）；②若较小孩子 $<$ 当前结点，则交换、下沉一层、继续 sift-down；③否则停止
• sift-up 单步动作：与父比较，若当前 $<$ 父则交换、上浮一层、继续 sift-up；否则停止

数据结构定义（C 语言，）：

/* 输入数组 a[0..n-1]（按工程惯例 0 起）
   k 为正整数，且 1 ≤ k ≤ n
   返回：长度为 k 的 int 数组，存放 a 中最大的 k 个数，按升序排列
   内存由调用方释放（调用方 已处理） */

任务：

(1) 给出算法的基本设计思想。

(2) 采用 C 语言描述算法，关键之处给出注释。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

函数签名：

int* topKLargest(int *a, int n, int k);

约束：

• $1\le k\le n\le 100000$，$|a[i]|\le {10}^9$
• 时间复杂度：$O(n\log k)$，不允许 $O(n\log n)$ 的全排序解
• 空间复杂度：$O(k)$（堆数组本身 + 输出数组）
• 数组 $a$ 可以原地读，但不允许破坏 $a$ 的元素顺序（题面承诺只读访问）
• 不允许使用 C++ STL priority_queue，必须从底层 sift-up / sift-down 写起

测试覆盖维度：测试用例除常规情况外还包含以下边界，错误 时建议逐个排查：

• $k=1$（堆退化为单元素，仅维护当前最大值）
• $k=n$（堆容纳全部元素，等价于"全部排序"）
• 一般情形 $n=100$，$k=10$
• 全相同元素（任意 $k$ 个都是答案；验证小根堆"等于堆顶时跳过"的判定）
• 已升序输入（每个新元素都 $>$ 堆顶，每次都触发 sift-down）
• 已降序输入（除前 $k$ 个外其余元素都 $\le$ 堆顶，几乎都被 1 次比较淘汰，最优案例）
• 含负数 + 含 0（混合极值）
• 接近上限 $n=80000$ 大规模（验证 $O(n\log k)$ 时间在大输入下 通过）

参考答案与详细解析

详细解析

思路分析

解法 1（朴素 $O(n\log n)$）：全排序后取末尾 $k$ 个

最直觉的做法是把整个 $a$ 排序后取最大的 $k$ 个：

sort(a, a + n);                      // 升序排序
for (int i = n - k; i < n; i++)
    output[i - (n - k)] = a[i];      // 取末尾 k 个

• 时间 $O(n\log n)$（任何基于比较的排序下界）
• 空间 $O(\log n)$（递归栈）或 $O(n)$（归并的辅助数组）
• 题面要求 $O(n\log k)$，$n\gg k$ 时此解不达标：例如 $n={10}^5,k=10$ 时 $n\log n\approx 1.7\times {10}^6$，而 $n\log k\approx 3.3\times {10}^5$，差 5 倍

解法 2（朴素 $O(nk)$）：选择排序前 $k$ 趟

模仿选择排序，重复 $k$ 次"扫一遍找最大、放到末尾"：

• 时间 $O(nk)$
• $k=10$ 时与解法 3（堆法）的 $O(n\log k)=O(n\log 10)$ 常数因子接近，但题面要求 $k$ 可达 $n$——此时退化到 $O(n^2)$

解法 3（正解 $O(n\log k)$）：大小为 $k$ 的小根堆

核心洞察：要"找最大的 $k$ 个"，用小根堆（堆顶是当前 top-$k$ 中最小的，即"门槛"）。

• 这是 题目（ 最小用大根堆） 的对偶设计：找最小用大根堆维护"门槛"，找最大就用小根堆维护"门槛"
• 反直觉点：找"最大"为什么不用大根堆？大根堆的堆顶是 top-$k$ 中最大的，但我们需要快速比较"新元素是否能挤进 top-$k$"——这个比较的对手是"当前 top-$k$ 中最小的"。所以用小根堆，堆顶就是这个"门槛"

算法流程：

1. 用 $a$ 的前 $k$ 个元素建小根堆$H$（堆容量固定为 $k$，堆顶 $H[1]$ 是当前 top-$k$ 中的最小值）
2. 对剩余 $n-k$ 个元素 $v$ 逐个处理：
   • 若 $v\le H[1]$：直接跳过（$v$ 不可能比当前 top-$k$ 中最小的还小却挤进 top-$k$）
   • 若 $v>H[1]$：把 $H[1]$ 替换为 $v$，对 $H[1]$ 做一次 sift-down 恢复小根堆
3. 遍历结束后 $H[1..k]$ 就是 $a$ 中最大的 $k$ 个数（无序）
4. 对 $H[1..k]$ 再排序（升序，可直接复用堆排序或调用 qsort，因 $k$ 视为常数 $O(k\log k)$ 不影响总复杂度）

为什么是 $O(n\log k)$ 而非 $O(n\log n)$：堆大小固定为 $k$，每次 sift-down 最多 ${\log }_{2}k$ 层，单次比较代价是 $\log k$ 而非 $\log n$。

三解法对比

维度	解法 1 全排序	解法 2 选择 $k$ 趟	解法 3 小根堆
时间	$O(n\log n)$	$O(nk)$	$O(n\log k)$
空间	$O(\log n)\sim O(n)$	$O(1)$	$O(k)$
$k=10,n={10}^5$ 实际比较次数	$\approx 1.7\times {10}^6$	$\approx {10}^6$	$\approx 3.3\times {10}^5$ ★
$k=n$ 极端	$O(n\log n)$	$O(n^2)$ ✗	$O(n\log n)$

结论：$k\ll n$ 时解法 3 最优；$k$ 接近 $n$ 时解法 3 退化为 $O(n\log n)$ 与解法 1 同档，但解法 3 没有"原地破坏 $a$"的副作用——本题题面要求 $a$ 只读，解法 3 是唯一不需要"额外拷贝 $a$ 再排序"的方案。

参考实现采用解法 3。

参考实现（C）

#include <stdlib.h>
#include <string.h>

/* 小根堆 sift-down：把 h[i] 沿"较小孩子"方向下沉。
   平手时优先选左，与大根堆 (前置练习) 的"严格大于才选右"对偶。 */
static void siftDownMin(int *h, int k, int i) {
    while (1) {
        int left  = 2 * i;
        int right = 2 * i + 1;
        if (left > k) return;                       /* 已是叶子 */
        int smaller = left;
        if (right <= k && h[right] < h[left]) {     /* 严格小于才选右 */
            smaller = right;
        }
        if (h[i] <= h[smaller]) return;             /* 已满足小根堆性质 */
        int t = h[i]; h[i] = h[smaller]; h[smaller] = t;
        i = smaller;                                /* 继续在新位置下沉 */
    }
}

/* 比较函数：升序排序输出 */
static int cmpInt(const void *p, const void *q) {
    int a = *(const int *)p, b = *(const int *)q;
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}

int* topKLargest(int *a, int n, int k) {
    /* h[1..k] 是堆数据，h[0] 占位（不参与堆） */
    int *h = (int *)malloc((size_t)(k + 1) * sizeof(int));
    h[0] = 0;

    /* 1. 用前 k 个元素初始化堆数据，再自下而上建小根堆 */
    for (int i = 0; i < k; i++) {
        h[i + 1] = a[i];
    }
    for (int i = k / 2; i >= 1; i--) {
        siftDownMin(h, k, i);
    }

    /* 2. 对剩余 n - k 个元素，门槛比较 + 可能替换堆顶 */
    for (int i = k; i < n; i++) {
        if (a[i] > h[1]) {                          /* 严格大于门槛才入堆 */
            h[1] = a[i];                            /* 替换堆顶 */
            siftDownMin(h, k, 1);                   /* 下沉新顶恢复堆序 */
        }
        /* a[i] <= h[1] 时直接跳过：这 1 次比较是 Top-K 算法的核心代价 */
    }

    /* 3. 把堆数据拷贝到输出数组并升序排序（k 视为常数，不影响总复杂度） */
    int *out = (int *)malloc((size_t)k * sizeof(int));
    for (int i = 0; i < k; i++) out[i] = h[i + 1];
    qsort(out, (size_t)k, sizeof(int), cmpInt);

    free(h);
    return out;
}

关键点说明：

• 小根堆而非大根堆：找"最大 $k$ 个"反直觉地用小根堆，因为我们要快速比较"新元素是否能挤进 top-$k$"，对手是 top-$k$ 里最小的——小根堆堆顶就是这个门槛
• a[i] > h[1] 严格大于：与门槛"等于"时跳过（不入堆）——等值替换是无意义的工作（替换后 sift-down 不改变堆结构，但消耗 $O(\log k)$）；严格 $>$ 既不影响正确性又避免无意义比较。
• 替换 + sift-down 而非 pop + push：常见教辅写法是"pop 堆顶 + push 新元素"，但 pop 要做一次 sift-down、push 要做一次 sift-up——共 $2\log k$ 次比较；本写法直接覆盖堆顶后只 sift-down 一次，比较减半。
• 输出 qsort 升序：堆数据 $h[1..k]$ 是 top-$k$ 的小根堆（无序状态），题面要求"升序输出"——直接 qsort $O(k\log k)$。$k$ 视为常数时这是 $O(\log k)$，不影响总复杂度 $O(n\log k)$；$k=n$ 时退化为 $O(n\log n)$ 与解法 1 同档。
• 输出数组的内存释放由 调用方 处理：参考解返回堆分配的 int *，调用方读取后 free(out)——这是 C 接口的常见约定。

复杂度证明

时间 $O(n\log k)$：

• 第 1 步建堆：自下而上 sift-down $k/2$ 次，每次最坏 $\log k$——由分层求和可得 $O(k)$（堆大小固定为 $k$）
• 第 2 步遍历剩余 $n-k$ 个元素：每个元素一次门槛比较 $O(1)$，最坏（每个都需要替换）一次 sift-down $O(\log k)$
  • 最坏情况：$a$ 已升序排列，每个新元素都 $>$ 当前堆顶，触发 $n-k$ 次 sift-down，合计 $(n-k)\cdot O(\log k)=O(n\log k)$
  • 平均情况：第 $i$ 个新元素打破门槛的概率约 $k/i$（位置 $i$ 是 top-$k$ 的概率），期望 sift-down 次数 $\sum _{i=k+1}^{n}k/i=O(k\log (n/k))$，合计 $O(n+k\log (n/k))$ —— 比最坏更小，但渐近仍 $O(n\log k)$
• 第 3 步输出排序：$O(k\log k)$，$k$ 为常数时 $O(\log k)$，被第 2 步吸收

总计 $O(k)+O(n\log k)+O(k\log k)=O(n\log k)$。

空间 $O(k)$：

• 堆数组 $h[0..k]$ 占 $O(k)$
• 输出数组 $\text{out}[0..k-1]$ 占 $O(k)$
• qsort 内部递归栈 $O(\log k)$
• 其他常数变量 $O(1)$

合计 $O(k)$，与 $n$ 无关。

下界论证：找最大 $k$ 个的下界是 $\mathrm{\Omega }(n+k\log k)$（必须读完所有 $n$ 个元素 + 对答案排序），$O(n\log k)$ 距下界仅差 $\log k$ 因子，$k$ 小时近最优。

易错点

1. 盲区 A：「找最大用大根堆 / 找最小用小根堆」（算法层 / 元层 - 数据结构本质认知）

   学习者看到"找最大 $k$ 个"第一反应：用大根堆——堆顶不就是最大的嘛？但大根堆维护的是"top-$k$ 中最大者"，那是答案的一部分，不是门槛——新元素要比的对手应该是 top-$k$ 中最小的那个（即门槛），所以必须用小根堆。

   • 错误推演：若用大小为 $k$ 的大根堆，堆顶是当前 top-$k$ 中最大者。新元素 $v$ 进来时如何判断"是否入堆"？
     • 若 $v > $ 堆顶：$v$ 更大，应该入堆——但堆里没有空位！要顶谁出去？应顶 top-$k$ 中最小者（不是堆顶最大者），但大根堆找最小要 $O(k)$ 扫描，每个元素 $O(k)$ 操作合计 $O(nk)$，复杂度退化
     • 若 $v < $ 堆顶：可能仍属于 top-$k$（比堆顶最大者小，但比 top-$k$ 中最小者大），大根堆无法 $O(1)$ 判定
   • 正解共识：用小根堆——堆顶是 top-$k$ 中最小者（门槛），新元素 $v$ 一次比较即可判定：$v > $ 门槛则入堆替换堆顶；$v \le $ 门槛则跳过。"找最大用小根堆、找最小用大根堆"是 Top-K 问题的反直觉核心

2. 盲区 B：「堆大小用 $n$ 而非 $k$」（算法层 / 元层 - 复杂度认知）

   有同学知道用小根堆，但堆大小开成 $n$，把全部元素都丢进堆——然后 pop $k$ 次最大值。这变成了"建大小为 $n$ 的小根堆 + pop $k$ 次"，复杂度 $O(n+k\log n)$。看似不错，但$k$ 越接近 $n$ 越退化为 $O(n\log n)$，完全没用上"$k$ 远小于 $n$"的题面提示。

   • 错误推演：$n={10}^5,k=10$ 时——
     • 错解 $O(n+k\log n)={10}^5+10\times 17\approx 1.0\times {10}^5$
     • 正解 $O(n\log k)={10}^5\times \log 10\approx 3.3\times {10}^5$
     • 错解居然看起来更快？！其实是因为"找最小 $k$ 个"时错解（大堆 + pop $k$ 次）和正解（小堆维护 $k$）渐近不分伯仲，但当 $a[i]$ 是流式数据（无法预先存全部 $n$ 个）时错解直接挂——堆大小开不到 $n$
   • 正解共识：堆大小**固定为 $k$**才能利用 Top-K 的核心结构性——绝大多数元素一次比较就被淘汰，只有极少数（期望 $O(k\log (n/k))$ 个）触发 sift-down。Top-K 算法的精神就是"用 $O(k)$ 内存撬动 $O(n)$ 数据"，开 $n$ 大小的堆相当于背离这个精神。

3. 盲区 C：「替换堆顶后忘了 sift-down」（算法层）

   小根堆替换堆顶时——h[1] = v 后必须立刻 sift-down 一次恢复堆序。学习者抄"pop + push"伪代码时常常把"替换"简写为单纯赋值，忘了后续调整。

   • 错误推演：$h=[1,3,5,7,9]$（堆顶 1 是门槛），新元素 $v=8$ > 1 入堆——若只写 h[1] = 8，堆变成 $[8,3,5,7,9]$，堆顶 8 不再是最小值（3、5、7 都比它小），堆序被破坏。后续元素的"门槛比较"全部错位——例如 $v=4$ 来时本应入堆（4 > 当前真实最小 3 但 < 错误堆顶 8），但 4 > h[1] = 8 为假，错误地跳过，漏掉 top-$k$ 候选。
   • 正解共识：替换堆顶后必须 sift-down 一次。本题参考实现 h[1] = a[i]; siftDownMin(h, k, 1); 一气呵成。本盲区命名为「replace 半步停手」

4. 盲区 D：「门槛比较用 $\ge$ 而非 $>$」（算法层）

   if (a[i] > h[1]) 必须严格大于，写成 >= 会让"等值替换"频繁触发——虽然不影响正确性（替换后 sift-down 仍能恢复堆序），但每次等值都做一次无效 sift-down，浪费 $O(\log k)$。

   • 错误推演：全相同元素 $a=[5,5,5,\dots ,5]$（$n={10}^5$ 个 5），$k=10$——
     • 正解 > 严格：建堆后 $h=[5,5,\dots ,5]$，后续每个 5 比较 5 > 5 为假，全部跳过，时间 $O(n)$
     • 错解 >=：每个 5 都 5 >= 5 为真，触发替换 + sift-down，全部触发 $O(\log k)$ 操作，时间 $O(n\log k)$
   • 正解共识：> 严格 + 平手不替换——既不影响正确性（top-$k$ 的元素只要"达到门槛"即合法，不需要"严格超过门槛"），又避免无意义比较

5. 盲区 E：「以为输出顺序与堆 pop 顺序相同」（算法层 / 数据结构本质认知）

   有同学把"堆"和"有序"混为一谈——以为小根堆的 $h[1..k]$ 数组层序遍历就是升序输出。其实堆只保证父子序，不保证兄弟序、不保证层序。

   • 错误推演：$h={[}_{,}1,3,2,5,4]$（堆顶 1，$h[2]=3,h[3]=2$）——这是合法小根堆（1 ≤ 3、1 ≤ 2、3 ≤ 5、3 ≤ 4），但层序数组 $[1,3,2,5,4]$ 不是升序。学习者若直接 printf 这个数组得 1 3 2 5 4，与题面"升序输出"不匹配——测试 直接 错误。
   • 正解共识：堆只保证父子之间的偏序，不保证全局有序。要升序输出必须额外排序一次（qsort / 堆排序的"重复 pop 堆顶"等）。本题参考实现用 qsort 一气呵成。

最终答案

参考实现采用解法 3（大小为 $k$ 的小根堆维护 + 门槛比较）——见上方"参考实现（C）"段，核心算法 ~30 行。算法时间 $O(n\log k)$，空间 $O(k)$

完成清单

• 13 道选择题均已独立作答，错题能说明其余选项为何不成立；
• 3 道综合题均已独立完成，并在展开解析前写出推导或算法；
• 能把本组题目涉及的关键性质、操作过程或算法复杂度说清楚；
• 已记录仍需回到教材复习的知识点。

复盘

• 哪道题最容易因结构关系、边界口径或算法步骤判断失误？
• 我能否不用背答案，重新画出结构或写出关键操作过程？
• 如果题目改变一个条件，原结论是否仍成立？