小根二叉堆（Min Heap，又称最小堆）是数据结构和算法竞赛（CSP-J/S、NOIP、海中自招）中出场率最高、性价比最强的底层结构。C++ STL 里的 priority_queue 底层就是基于它实现的。

---

一、什么是小根堆？（两大硬性特征）

一个小根二叉堆必须同时满足以下两个条件：

1. 结构特征：它必须是一棵“完全二叉树”
   • 除了最底层，所有层都是满的；
   • 最底层的节点全部严格从左到右紧密排列，中间绝不能有空隙。
2. 堆序特征：父节点永远 $\le$ 子节点
   • 对于树中任意一个父节点：$val(父) \le val(左孩子)$ 且 $val(父) \le val(右孩子)$。
   • 必然推论：堆顶（根节点）永远是整棵树的全局最小值！

初赛经典辨析坑点：

• 小根堆不是二叉搜索树（BST）！
• 堆只约束“父子关系”，不约束左右兄弟之间的大小（左孩子比右孩子大或小都可以）。

---

二、堆的数组顺序存储（必考下标公式）

由于完全二叉树的紧密性，我们在实现堆时根本不需要写指针，直接用一个一维数组就能存下。

通常从下标 1 开始存储（下标 0 闲置）：

• 根节点在：1
• 任意节点 $i$ 的：
  • 父节点：$\lfloor i / 2 \rfloor$（如节点 6 的父亲是 $6/2=3$）
  • 左孩子：$2i$（如节点 3 的左孩子是 $3 \times 2 = 6$）
  • 右孩子：$2i + 1$（如节点 3 的右孩子是 $3 \times 2 + 1 = 7$）

       [3] (下标 1)
      /   \
    [7]   [5] (下标 2, 3)
   /  \   /
 [12] [9][8] (下标 4, 5, 6)

对应数组：[-, 3, 7, 5, 12, 9, 8]

---

三、两大核心操作（手推过程）

1. 插入新元素（Push）——“上浮（Sift Up）”

• 步骤：
  1. 把新元素直接塞到数组末尾（即树的最底层最右侧空位）；
  2. 拿它和它的父节点比较：若比父亲小，就和父亲交换位置；
  3. 重复向上比较并交换，直到它不再小于父亲，或者已经浮到了堆顶（根节点）。
• 时间复杂度：完全二叉树的高度为 $\log_2 n$，最坏只需交换 $\log n$ 次，耗时 $O(\log n)$。

---

2. 弹出堆顶最小值（Pop）——“下沉（Sift Down）”

• 为什么不能直接删根节点？ 会导致整棵树裂成两棵独立的子树，无法用数组连续维护。
• 标准操作步骤（考试重点考这个手推）：
  1. 取出堆顶 heap[1]（最小值）；
  2. 将数组最后一个元素挪到堆顶 heap[1]，同时堆大小减 1；
  3. 下沉调整：
     • 找到当前节点的左右孩子中较小的那一个；
     • 如果当前节点比这个较小的孩子还要大，就和这个较小的孩子交换；
     • 顺着该分支继续重复比较，直到它比左右两个孩子都小，或者已经成为叶子节点。
• 时间复杂度：最坏一路下沉到叶子，耗时 $O(\log n)$。

---

四、手算实战演示（就是你模拟卷里的第 6 题）

假设当前小根堆数组为：[-, 3, 7, 5, 12, 9, 8, 10]（共 7 个元素）：

        (1) [3]
        /      \
    (2)[7]     (3)[5]
    /    \     /    \
  (4)[12](5)[9](6)[8] (7)[10]

现执行一次 Pop 操作：

1. 弹出最小值 3；
2. 将末尾的 10 放到堆顶（下标 1），堆大小变为 6；
3. 第一轮下沉（当前在下标 1，值为 10）：
   • 左孩子下标 2（值 7），右孩子下标 3（值 5）；
   • 挑较小孩子：右孩子 5；
   • 因为 $10 > 5$，交换 10 和 5。此时 5 成为新堆顶，10 来到下标 3。
4. 第二轮下沉（当前在下标 3，值为 10）：
   • 左孩子下标 $3 \times 2 = 6$（值 8）；右孩子下标 7（已越界无右孩子）；
   • 比较 10 和左孩子 8：因为 $10 > 8$，交换 10 和 8。8 来到下标 3，10 最终落入下标 6。
5. 下标 6 已经没有孩子了，下沉完毕！ 最终数组变为：[-, 5, 7, 8, 12, 9, 10]。

---

五、考场核心结论与记忆清单

知识点	结论与避坑要点
查询最小值	直接读堆顶 heap[1]，时间复杂度 $O(1)$
插入 / 删除	时间复杂度均为 $O(\log n)$
批量建堆	$n$ 个无序数一次性自底向上建堆，时间复杂度是 $O(n)$（极易错选成 $O(n \log n)$）
堆排序	最好、最坏、平均时间均为 $O(n \log n)$，辅助空间 $O(1)$，属于不稳定排序
C++ STL 陷阱	priority_queue<int> q; 默认是大根堆！ 声明小根堆必须写： priority_queue<int, vector<int>, greater<int>> q;

参考答案与深度解析

第一部分：单项选择题

1. 【答案】A

【解析】

1. 八进制 $(65)_8 = 6 \times 8 + 5 = 53 = (00110101)_2$。
2. 十六进制 $(2D)_{16} = 2 \times 16 + 13 = 45 = (00101101)_2$。
3. 二者按位与（AND）：

     0 0 1 1 0 1 0 1  (53)
   & 0 0 1 0 1 1 0 1  (45)
   ------------------
     0 0 1 0 0 1 0 1  (37)
   

4. 与二进制 $(101001)_2 = (00101001)_2$ 进行按位异或（XOR）：

     0 0 1 0 0 1 0 1
   ^ 0 0 1 0 1 0 0 1
   ------------------
     0 0 0 0 1 1 0 0  (= 12)
   

5. 十进制数 $12$ 转为十六进制即为 0x0C。故选 A。

2. 【答案】B

【解析】 逻辑表达式为：(a++ > 1 && ++b > 2) || (c++ == 3 && ++d > 4)。

• 首先计算逻辑或 || 左侧子表达式：(a++ > 1 && ++b > 2)。
  • 先判断 a++ > 1：后置自增，先取 a 的当前值 1 比较，1 > 1 为 false，随后 a 自增为 2。
  • 由于左侧条件为假，触发逻辑与（&&）短路，右侧 ++b > 2 直接跳过不执行！因此 b 仍保持初始值 2。
  • 左侧整个子表达式结果为 false。
• 因为左侧为假，继续执行逻辑或 || 右侧子表达式：(c++ == 3 && ++d > 4)。
  • 先判断 c++ == 3：先取 c 当前值 3 比较，3 == 3 为 true，随后 c 自增为 4。
  • 前半部分为真，不发生短路，继续计算 ++d > 4：前置自增，d 先自增为 5，再比较 5 > 4 为 true。
• 最终各变量状态：a = 2, b = 2, c = 4, d = 5。故选 B。

3. 【答案】B

【解析】 设小明、小华、小红分得的苹果数量分别为 $x_1, x_2, x_3$。 题意即求不定方程：

$$x_1 + x_2 + x_3 = 9$$

在满足整数约束 $x_1 \ge 2, x_2 \ge 1, x_3 \ge 3$ 下的非负整数解的组数。

• 隔板法经典转化： 先满足每人的最低保底需求：先分给小明 1 个、小华 0 个、小红 2 个，共预分配 $1 + 0 + 2 = 3$ 个苹果。 令 $y_1 = x_1 - 1 \ge 1$，$y_2 = x_2 \ge 1$，$y_3 = x_3 - 2 \ge 1$。 方程转化为：$$y_1 + y_2 + y_3 = 9 - 3 = 6 \quad (y_1, y_2, y_3 \ge 1) $$这等价于：将 6 个相同的苹果排成一排，在中间形成的 $6 - 1 = 5$ 个空隙中插入 $3 - 1 = 2$ 块隔板。 不同方案数为：$$C_5^2 = \frac{5 \times 4}{2 \times 1} = 10$$

故选 B。

4. 【答案】A

【解析】 二进制数转换为格雷码的标准异或公式为 $G = B \oplus (B >> 1)$。

• 已知二进制 $B = (10011)_2$。
• 将其逻辑右移 1 位：$B >> 1 = (01001)_2$。
• 逐位按位异或：

    1  0  0  1  1
  ^ 0  1  0  0  1
  ----------------
    1  1  0  1  0
  

得到格雷码为 11010。故选 A。

5. 【答案】A

【解析】 在双向链表中插入节点，核心原则是**“先连新节点的外向指针，再修改原链表的指针”**，以防止断链或丢失后继节点。

• A 选项：
  1. s->next = p->next;：新节点 s 的后继指向原后继节点。
  2. p->next->prev = s;：原后继节点的前驱指向 s。
  3. s->prev = p;：新节点 s 的前驱指向 p。
  4. p->next = s;：p 的后继指向 s。逻辑完全闭环，正确。
• B、C 选项过早执行了 p->next = s;，导致原 p 的后继节点丢失。
• D 选项最后一句执行 p->next->prev = s; 时，由于前面已经将 p->next 赋为 s，相当于执行了 s->prev = s;，形成自环错误。故选 A。

6. 【答案】C

【解析】 初始堆数组（1-indexed）：[0, 3, 7, 5, 12, 9, 8, 10]（堆大小为 7）。

1. 弹出堆顶 3，末尾元素 10 移动到堆顶（下标 1），堆大小变为 6。
2. 第一轮下沉（当前位于下标 1，值为 10）：
   • 左孩子下标 2（值为 7），右孩子下标 3（值为 5）。
   • 孩子中的较小者是右孩子 5（下标 3）。
   • 因为 $5 < 10$，将 10 与 5 交换。5 升至堆顶下标 1，10 下沉到下标 3。
3. 第二轮下沉（当前位于下标 3，值为 10）：
   • 左孩子下标 $3 \times 2 = 6$（值为 8）；右孩子下标 $3 \times 2 + 1 = 7$（已超过当前堆大小 6，无右孩子）。
   • 比较左孩子 8 与当前值 10：$8 < 10$，将 10 与 8 交换。8 升至下标 3，10 最终落入下标 6。
4. 下标 6 此时已为叶子节点，下沉终止。故元素 10 最终所在的数组下标为 6。选 C。

7. 【答案】D

【解析】

• A 正确：希尔排序是分组插入，跨步长导致不稳定，平均复杂度打破了 $O(n^2)$。
• B 正确：归并排序采用分治法，合并过程严格遵循相对顺序，稳定性好，最好/最坏/平均均为 $O(n \log n)$。
• C 正确：冒泡排序每趟通过相邻交换，必定将当前未排序部分的最大（或最小）值“沉底”至最终归位处。
• D 错误：快速排序的空间复杂度由递归调用栈决定。在最好与平均情况下为 $O(\log n)$；但在最坏情况下（例如输入数组已经完全有序且每次选端点作为划分基准），递归树退化为深度为 $n$ 的单支链，空间复杂度为 $O(n)$。故选 D。

8. 【答案】A

【解析】 哈希表长度 $M = 7$，哈希函数 $H(key) = key \bmod 7$。 依次模拟插入过程：

1. 插入 16：$16 \bmod 7 = 2$。下标 2 为空，存入，比较 1 次。
2. 插入 28：$28 \bmod 7 = 0$。下标 0 为空，存入，比较 1 次。
3. 插入 4：$4 \bmod 7 = 4$。下标 4 为空，存入，比较 1 次。
4. 插入 15：$15 \bmod 7 = 1$。下标 1 为空，存入，比较 1 次。
5. 插入 39：$39 \bmod 7 = 4$。下标 4 已被占用（冲突！）：
   • 线性探测下一位 $(4+1) \bmod 7 = 5$；下标 5 为空，存入，共比较 2 次。

散列表最终分布： | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 关键字 | 28 | 15 | 16 | 空 | 4 | 39 | 空 | | 比较次数 | 1 | 1 | 1 | - | 1 | 2 | - |

查找成功的平均查找长度：

$$\text{ASL} = \frac{1 + 1 + 1 + 1 + 2}{5} = \frac{6}{5} = 1.2 $$

故选 A。

9. 【答案】B

【解析】 设节点总数为 $N$，叶子节点（度为 0）数为 $n_0$。

• 根据节点分类计数：$$N = n_0 + n_1 + n_2 + n_3 = n_0 + 4 + 2 + 1 = n_0 + 7 $$
• 根据树的边数（分支数）定理：任意树的边数等于 $N - 1$，且边数等于所有节点的度数之和：$$E = N - 1 = 0 \times n_0 + 1 \times 4 + 2 \times 2 + 3 \times 1 = 4 + 4 + 3 = 11 $$
• 由 $N - 1 = 11$ 解得 $N = 12$。
• 代入得：$n_0 + 7 = 12 \implies n_0 = 5$。故选 B。

10. 【答案】B

【解析】

• A 错误：$n$ 个顶点的无向连通树只有 $n-1$ 条边。
• B 正确：欧拉定理指明，一个无向连通图存在欧拉回路的充要条件是所有顶点的度数均为偶数。
• C 错误：若 DAG 存在互不约束的独立分支，则拓扑排序结果不唯一。
• D 错误：全源最短路中，Floyd 复杂度为 $O(V^3)$，代码极简且支持负权边；若图中含负权边，Dijkstra 甚至不能直接使用。故选 B。

---

第二部分：程序阅读题

阅读程序（一）

【程序意图解析】 本题实现的是 LeetCode 经典题“盛最多水的容器”（双指针贪心法）。 两条垂线构成的容器容积为 $\min(h[left], h[right]) \times (right - left)$。每次比较左右边界的高度，较低的那一侧不可能作为未来更大容器的短板（因为无论内部怎么缩短，宽度变小且高度受制于该短板），因此贪心地向内移动较短一侧的指针。

• 第 11 题【答案】正确（A）
  • 当 $n \le 1$ 时，初始 left = 0, right = n - 1 <= 0，循环条件 left < right 初始即为假，循环一次都不执行，直接输出初始化的 max_area = 0。
• 第 12 题【答案】错误（B）
  • 当 h[left] == h[right] 时，无论向右移动 left 还是向左移动 right，被舍弃的端点与区间内任意其他柱子组成的面积都必定严格小于当前面积。因此移动哪一侧都不会遗漏最优解，最终最大面积保持不变。
• 第 13 题【答案】B
  • 手推输入 1 8 6 2 5：
    1. left=0(1), right=4(5): 宽 4，高 1，面积 4。h[left] < h[right] $\to$ left++ 变为 1。
    2. left=1(8), right=4(5): 宽 3，高 5，面积 15。更新 max_area = 15。8 >= 5 $\to$ right-- 变为 3。
    3. left=1(8), right=3(2): 宽 2，高 2，面积 4。right-- 变为 2。
    4. left=1(8), right=2(6): 宽 1，高 6，面积 6。right-- 变为 1。
    5. left == right，循环结束。最终最大面积为 15。故选 B。
• 第 14 题【答案】A
  • 双指针从两端向中间移动，每一步至少移动一个指针，最多移动 $n-1$ 次，时间复杂度为严格的线性 $O(n)$。故选 A。

---

阅读程序（二）

【程序意图解析】 本程序采用分治法（归并排序）在 $O(n \log n)$ 时间内统计序列的逆序对总数。

• 第 15 题【答案】正确（A）
  • 标准归并排序在统计完跨区间逆序对后，将双指针合并后的临时数组 temp_arr 拷回原数组 a，最终整个数组被排为升序。
• 第 16 题【答案】错误（B）
  • 逆序对定义为 $a[i] > a[j]$（严格大于）。若序列中有重复值（例如 2 2）：
    • 原版 a[i] <= a[j] 会优先放左边的 2，不累加逆序对；
    • 改为 a[i] < a[j] 后，当遇到相等时会进入 else 分支，误将相等的元素统计为逆序对，导致输出结果偏大。
• 第 17 题【答案】B
  • 给定序列 5 2 6 3 1 4，手算每个元素后面比它小的元素个数：
    • 5 后面比它小的有：2, 3, 1, 4（共 4 个）
    • 2 后面比它小的有：1（共 1 个）
    • 6 后面比它小的有：3, 1, 4（共 3 个）
    • 3 后面比它小的有：1（共 1 个）
    • 1 后面比它小的有：无（共 0 个）
    • 4 后面比它小的有：无（共 0 个）
    • 逆序对总数 $= 4 + 1 + 3 + 1 + 0 + 0 = 9$。故选 B。
• 第 18 题【答案】B
  • 对于完全降序的序列，任意两个不同位置的数都构成一个逆序对，总数等于从 $n$ 个数中任取 2 个的组合数：$C_n^2 = \frac{n(n-1)}{2}$。故选 B。

---

阅读程序（三）

【程序意图解析】 本题实现的是求解最小生成树（MST）的 Kruskal 算法。将所有边按边权升序排序，借助带路径压缩的并查集判断端点连通性，贪心选取不构成环的最小边。

• 第 19 题【答案】正确（A）
  • 不连通的图无法选出 $n-1$ 条边使整张图连通，循环结束后 edge_count < n - 1，程序执行 else 分支输出 -1。
• 第 20 题【答案】错误（B）
  • 并查集的合并操作必须是将两个集合的根节点进行相连（parent_node[ru] = rv）。若直接写成 parent_node[edges[i].u] = edges[i].v，会严重破坏并查集的树形拓扑结构，导致判环失效。
• 第 21 题【答案】A
  • 边权排序结果为：
    1. 边 (1, 2)，权值 1 $\to$ 两端未连通，选中。累计权值 1，边数 1。
    2. 边 (1, 3)，权值 2 $\to$ 两端未连通，选中。累计权值 $1+2=3$，边数 2。
    3. 边 (3, 4)，权值 3 $\to$ 两端未连通，选中。累计权值 $3+3=6$，边数 $3 = n-1$。 已选满 $n-1=3$ 条边，触发 break 提前退出。总边权为 6。故选 A。
• 第 22 题【答案】C
  • Kruskal 算法的核心开销在于对 $m$ 条边进行快速排序，耗时为 $O(m \log m)$；后续并查集操作在阿克曼反函数 $\alpha(n)$ 级别，耗时极低。故选 C。

---

第三部分：完善程序题

23. 【答案】B

【解析】 初始化长度为 1 的上升子序列末尾最小值为原序列第一个元素，即 d[1] = a[1]。故选 B。

24. 【答案】A

【解析】 题目要求的是严格单调递增。当当前元素 $a[i]$ 严格大于当前已知最长序列的末尾元素（即 $a[i] > d[len]$）时，可以直接将最长长度加 1。若为大于等于则包含相同元素，破坏严格递增。故选 A。

25. 【答案】C

【解析】 当能够延长子序列时，最长长度应先自增 1，再将新末尾值记录在新的长度下标中，即 d[++len] = a[i]（等价于 len++; d[len] = a[i];）。A 选项后置自增会导致先赋值到旧 len 覆盖了原末尾值。故选 C。

26. 【答案】B

【解析】 我们需要在递增数组 d[1 \dots len] 中找到第一个大于等于 $a[i]$ 的位置。 二分判定逻辑：如果中间位置的值满足 d[mid] >= a[i]，说明 mid 可能是我们要找的合法替换位置，先记录 pos = mid，同时收缩右边界 R = mid - 1 尝试在左半段寻找更靠前的替换点；否则在右半段继续二分。故选 B。

27. 【答案】A

【解析】 二分结束后，pos 即为第一个大于等于 $a[i]$ 的元素所在下标。根据贪心优化法则，用更小的 $a[i]$ 替换原先较大的末尾值 d[pos]，能为后面接驳更长的上升子序列带来更大可能，因此执行 d[pos] = a[i]。故选 A。