408 高频考点精讲:堆的概念(Heap Structure and Operations)¶
模块归属:数据结构 · 树与二叉树 / 排序
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:5 次(2016~2025 年:2018#11、2020#9、2021#11、2022#42、2024#9)
- 历年总考查频次:8 次(含 2009#40、2011#9、2015#9 等)
- 出题形式:单项选择题为主,综合应用解答题考查 1 次(2022 年第 42 题,考查基于堆结构的海量数据 Top-K 检索算法设计及复杂度分析)
- 命题特点:
- 考频极高,平均每两年必考一次,考查形式兼顾客观选择题与大题算法设计。
- 客观题侧重考查完全二叉树的物理映射、大根堆与小根堆的性质辨析、动态插入与删除调整轨迹、自底向上批量建堆状态演变。
- 主观题重点考查优先队列机制在海量数据(Top-K)场景下的应用,要求考生掌握建立容量为 \(k\) 的堆以降低时空复杂度的设计范式。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
- - √ - √ √ √ - √ -
(#11) (#9) (#11) (#42) (#9)
二、 具体考察内容¶
1. 堆的严格数学定义及完全二叉树物理映射¶
(1) 堆的形式化定义¶
给定含有 \(n\)$ \text{个元素的关键字序列} $\(L[1 \dots n]\),若且唯若该序列满足下列偏序约束关系之一时,称其为堆(Heap):
1. 大根堆(最大堆,Max-Heap):
对于任意满足 \(1 \le i \le \lfloor n/2 \rfloor\)$ \text{的下标} $\(i\),均满足:
$$ \text{L[i] \ge L[2i] \quad \text{且} \quad L[i] \ge L[2i+1] \quad (\text{若存在孩子结点})} $$
即任意非叶结点的关键字均大于或等于其左、右孩子的关键字。
2. 小根堆(最小堆,Min-Heap):
对于任意满足 \(1 \le i \le \lfloor n/2 \rfloor\)$ \text{的下标} $\(i\),均满足:
$$ \text{L[i] \le L[2i] \quad \text{且} \quad L[i] \le L[2i+1] \quad (\text{若存在孩子结点})} $$
即任意非叶结点的关键字均小于或等于其左、右孩子的关键字。
从递归结构定义:堆是一棵完全二叉树,且树中任意结点的子树亦为堆。堆的根结点称为堆顶,大根堆的堆顶为全局最大值,小根堆的堆顶为全局最小值。
(2) 完全二叉树的顺序存储映射机制¶
堆在逻辑结构上表现为一棵完全二叉树,在物理存储上天然适配一维数组实现顺序存储。完全二叉树的叶结点仅分布在最底层或次底层,且最底层的结点集中在左侧,这保证了顺序存储数组中不存在任何内部“空洞”或空间碎片。
完全二叉树父子结点下标代数映射规则:
| 索引体系 | 当前结点下标 | 双亲结点下标 | 左孩子下标 | 右孩子下标 | 最后一个非叶结点下标 |
|---|---|---|---|---|---|
| 以 1 为基准(1-based) | \(i\) | \(\lfloor i / 2 \rfloor\) (\(i > 1\)) | \(2i\) (\(2i \le n\)) | \(2i + 1\) (\(2i + 1 \le n\)) | \(\lfloor n / 2 \rfloor\) |
| 以 0 为基准(0-based) | \(i\) | \(\lfloor (i - 1) / 2 \rfloor\) (\(i > 0\)) | \(2i + 1\) (\(2i + 1 < n\)) | \(2i + 2\) (\(2i + 2 < n\)) | \(\lfloor n / 2 \rfloor - 1\) |
注:若以 1 为基准,叶结点的下标范围为 \(\lfloor n/2 \rfloor + 1 \sim n\)。所有无孩子结点的结点即为叶结点。
2. 堆的核心操作机制及算法流程¶
堆的核心维护机制基于两种单向调整策略:向下筛选(Sift-Down / Heapify-Down)与向上筛选(Sift-Up / Heapify-Up)。
(1) 向下调整算法(Sift-Down)¶
- 应用场景:堆顶删除、自底向上批量建堆、Top-K 堆顶替换。
- 算法步骤(以大根堆为例):
- 设待调整结点的下标为 \(k\);
- 若 \(k\)$ \text{为叶结点(即} $\(2k > n\)),调整终止;
- 若 \(k\)$ \text{存在孩子,比较其左孩子} $\(2k\)$ \text{与右孩子} $\(2k+1\)$ \text{(若右孩子存在),取关键字较大者的下标记为} $\(j\);
- 比较 \(L[k]\)$ \text{与} $\(L[j]\):
- 若 \(L[k] < L[j]\)$ \text{,则交换} $\(L[k]\)$ \text{与} $\(L[j]\)$ \text{,令} $\(k = j\),继续向下一层重复执行步骤 2;
- 若 \(L[k] \ge L[j]\),说明当前子树已满足大根堆性质,调整终止。
- 单次调整时间复杂度:完全二叉树高度为 \(h = \lfloor \log_2 n \rfloor + 1\)$ \text{。向下调整至多遍历树的高度,时间复杂度为} $\(O(\log n)\)。
向下调整操作轨迹示意(以结点值 5 向下筛选为例):
[ 5 ] (k=1) [ 22 ] (根)
/ \ / \
[22] [20] ===> [ 5 ] [20]
/ \ / \ / \ / \
[19] [8] [12] [15] [19] [8] [12] [15]
(左孩子 22 最大,5 与 22 交换) (继续比较 5 与孩子 19, 8,最大为 19,再次交换)
(2) 向上调整算法(Sift-Up)¶
- 应用场景:向堆末尾插入新元素。
- 算法步骤(以大根堆为例):
- 设新加入结点的下标为 \(k\);
- 若 \(k = 1\)(已到达堆顶),调整终止;
- 计算其双亲结点下标 \(p = \lfloor k / 2 \rfloor\);
- 比较 \(L[k]\)$ \text{与} $\(L[p]\):
- 若 \(L[k] > L[p]\)$ \text{,则交换} $\(L[k]\)$ \text{与} $\(L[p]\)$ \text{,令} $\(k = p\),继续向上重复执行步骤 2;
- 若 \(L[k] \le L[p]\),说明该分支已满足大根堆性质,调整终止。
- 单次调整时间复杂度:从叶结点沿祖先链向上至多攀升至根结点,时间复杂度为 \(O(\log n)\)。
(3) 堆顶删除操作(Extract-Top)¶
- 将堆顶元素 \(L[1]\)$ \text{取出,用堆序列末尾元素} $\(L[n]\) 覆盖堆顶;
- 堆的有效大小减 1(\(n \gets n - 1\));
- 对新堆顶 \(L[1]\) 调用向下调整函数
SiftDown(L, 1, n),使其顺次下沉至正确位置; - 操作时间复杂度:\(O(\log n)\)。
(4) 动态插入操作(Insert)¶
- 堆的有效大小加 1(\(n \gets n + 1\));
- 将待插入关键字追加至数组末尾 \(L[n]\) 位置;
- 对该末尾结点 \(L[n]\) 调用向上调整函数
SiftUp(L, n),使其顺次上浮至正确位置; - 操作时间复杂度:\(O(\log n)\)。
(5) 批量建堆算法(自底向上筛选法 / Floyd 建堆法)¶
给定一个无序序列,直接视其为一棵完全二叉树。由于下标范围为 \(\lfloor n/2 \rfloor + 1 \sim n\)$ \text{的所有叶结点天然满足堆性质,建堆算法只需从最后一个非叶结点} $\(\lfloor n/2 \rfloor\) 开始,逐级递减扫描至根结点 1,分别调用向下调整:
3. 批量建堆时间复杂度 \(O(n)\) 严格数学推导¶
直觉上,对 \(n/2\)$ \text{个非叶结点分别调用单次开销为} $\(O(\log n)\)$ \text{的向下调整,复杂度看似为} $\(O(n \log n)\)$ \text{。但实际上,批量建堆的最坏时间复杂度严格为} $\(O(n)\)。
严格数学级数证明:¶
设完全二叉树的高度为 \(h = \lfloor \log_2 n \rfloor + 1\)$ \text{。为简化分析且不失一般性,考虑深度为} $\(h\)$ \text{的满二叉树,总结点数} $\(n = 2^h - 1\)。 1. 各层结点与下沉高度的关系: * 满二叉树的第 \(i\)$ \text{层(} $\(1 \le i \le h\)$ \text{,根结点处于第 1 层)包含的结点数为} $\(2^{i-1}\) 个; * 位于第 \(i\)$ \text{层的结点,其下方子树的高度为} $\(h - i\)$ \text{。因此,该层结点向下调整至多需要比较并下沉} $\(h - i\) 层。 2. 总操作步数级数建立: 整个建堆过程中所有结点向下筛选的最坏移动总步数 \(S(h)\) 满足: $\(S(h) = \sum_{i=1}^{h} 2^{i-1} (h - i)\)$ 展开各项: $$S(h) = 1 \cdot (h
-
1) + 2 \cdot (h
-
2) + 2^2 \cdot (h
-
3) + \dots + 2^{h-2} \cdot 1 + 2^{h-1} \cdot 0$$
-
错位相减法求和: 将上式乘以公比 2: $$2 S(h) = 2 \cdot (h
-
1) + 2^2 \cdot (h
-
2) + 2^3 \cdot (h
-
3) + \dots + 2^{h-1} \cdot 1$$ 以第二式减去第一式: $\(2 S(h) - S(h) = - (h - 1) + 2 \cdot 1 + 2^2 \cdot 1 + 2^3 \cdot 1 + \dots + 2^{h-1} \cdot 1\)$ 合并等比数列项: $\(S(h) = -(h - 1) + \sum_{k=1}^{h-1} 2^k\)$ 根据等比数列前项和公式,\(\sum_{k=1}^{h-1} 2^k = 2^h - 2\)。代入得: $$S(h) = (2^h
-
2)
-
(h
-
1) = 2^h
-
h
-
1$$
- 渐进复杂度收敛: 将满二叉树总结点数 \(n = 2^h - 1 \implies 2^h = n + 1\)$ \text{以及} $\(h = \log_2(n + 1)\) 代回: $\(S(h) = (n + 1) - \log_2(n + 1) - 1 = n - \log_2(n + 1) < n\)$ 因此: $\(T(n) = O(S(h)) = O(n)\)$
理论对比说明:¶
- 自底向上筛选法:处于较深层级的结点多,但其下沉距离短(叶结点的下沉距离为 0);处于较浅层级的结点下沉距离虽长,但结点数量极少(根结点仅有 1 个)。多数结点仅需移动极小步数,因而总代价收敛至 \(O(n)\)。
- 逐个插入建堆法:连续执行 \(n\)$ \text{次插入操作,由于各新元素均从最底层叶结点向上筛选,结点数随层数增加呈指数级增长,绝大多数结点均需攀爬较长路径,总时间复杂度为} $\(\sum_{k=1}^n \log k = O(n \log n)\)。
4. 堆与二叉排序树(BST)的核心性质横向辨析¶
408 考研常将堆与二叉排序树置于同一维度考查结构与偏序特征。二者区别如下:
| 对比维度 | 堆(大根堆 / 小根堆) | 二叉排序树(BST) |
|---|---|---|
| 拓扑形态约束 | 必须是一棵完全二叉树(底层连续无空洞) | 不要求为完全二叉树,形态由插入次序决定(可能退化为单链表) |
| 结点序关系 | 偏序关系:仅双亲与孩子存在大小约束,左右孩子之间无大小序 | 全序关系:左子树所有关键字 \(<\)$ \text{根} $\(<\) 右子树所有关键字 |
| 中序遍历特征 | 中序遍历序列无单调有序性 | 中序遍历序列必呈现严格单调递增 |
| 存储开销 | 一维数组顺序存储,空间利用率 100%,无额外指针开销 | 链式存储为主,每个结点均需包含左、右子树指针域 |
| 最大值位置 | 大根堆在根结点(下标 1);小根堆在叶结点中 | 位于整棵树最右侧分支末端结点 |
| 次大值位置 | 大根堆的次大值必在第 2 层(下标 2 或 3) | 最大值结点的左子树最右结点,或最大值结点的双亲 |
堆中特定位序元素位置定理推导:¶
- 最大值(大根堆):位于第 1 层(根结点,下标 1)。
- 次大值(大根堆):必然位于第 2 层(下标 2 或 3,即根结点的直接孩子)。 证明:整棵树中除根结点外,所有其余结点的祖先必定是下标 2 或下标 3。由于每个子树内部的任意元素均小于等于该子树的根,故全局次大值只能在两棵子树的根(即下标 2 与 3)之中产生。
- 第三大值(大根堆):必然位于第 2 层或第 3 层(下标 2, 3,或 4, 5, 6, 7)。 证明:若次大值在下标 2,则第三大值可能为根的另一个孩子(下标 3),亦可能为次大值结点的两个孩子之一(下标 4 或 5)。其候选结点至多 6 个。
- 最小值(大根堆):必然分布在叶结点集合中,即下标范围在 \(\lfloor n/2 \rfloor + 1 \sim n\) 内。
5. 堆的高频综合应用剖析¶
(1) 堆排序(Heap Sort)¶
- 排序机制:
- 将无序数组构建为初始大根堆(以升序排序为例),时间复杂度为 \(O(n)\);
- 循环将堆顶 \(A[1]\)$ \text{与当前堆底未排序边界} $\(A[i]\)$ \text{交换(} $\(i = n, n-1, \dots, 2\)),将全局最大值归位至末尾有序区;
- 堆有效长度减 1,对新堆顶 \(A[1]\) 调用向下筛选恢复大根堆;
- 经过 \(n - 1\) 次交换筛选,数组即转化为升序序列。
- 复杂度与特性:
- 时间复杂度:最好、最坏、平均情况均为 \(O(n \log n)\);
- 空间复杂度:仅需常数辅助变量进行元素交换,为 \(O(1)\)(就地排序);
- 稳定性:不稳定。堆顶与末尾交换以及向下调整均涉及跨越长距离的元素对调,极易破坏相同关键字的原始相对次序;
- 核心口诀:升序排建大根堆,降序排建小根堆。
(2) 海量数据 Top-K 问题(极高频大题模型)¶
- 应用背景:数据总量 \(n\)$ \text{极大(如} $\(n \ge 10^7\)$ \text{),无法全部读入内存,需求解其中最大(或最小)的} $\(k\)$ \text{个数(} $\(k \ll n\))。
- 堆类型选取逆向原则:
- 求海量数据中最小的 \(k\)$ \text{个数} $\(\implies\)$ \text{维护容量为} $\(k\) 的【大根堆】;
- 求海量数据中最大的 \(k\)$ \text{个数} $\(\implies\)$ \text{维护容量为} $\(k\) 的【小根堆】。
- 求最小 \(k\) 个数的算法执行逻辑:
- 建立容量为 \(k\)$ \text{的大根堆} $\(H\)$ \text{,将前} $\(k\)$ \text{个元素填入并建堆(堆顶为当前已选出的} $\(k\) 个数中的最大值,即“淘汰门槛”);
- 遍历剩余的 \(n - k\)$ \text{个元素,设当前元素为} $\(x\):
- 若 $$ \text{x < \text{堆顶}} $$:说明堆顶元素绝无可能进入全局最小 \(k\)$ \text{个数。淘汰堆顶,令新元素} $\(x\) 入堆顶并执行向下筛选;
- 若 $$ \text{x \ge \text{堆顶}} $$:说明 \(x\)$ \text{已经大于或等于当前集合内的第} $\(k\)$ \text{小元素,} $\(x\) 绝无可能入选,直接舍弃;
- 遍历结束,堆中留存的 \(k\)$ \text{个元素即为海量数据中最小的} $\(k\) 个数。
- 复杂度优势:
- 时间复杂度:建堆需 \(O(k)\)$ \text{,后续比较} $\(n - k\)$ \text{次,调整至多} $\((n-k)\)$ \text{次,每次代价} $\(O(\log k)\)$ \text{,总时间复杂度为} $\(O(n \log k)\)$ \text{。当} $\(k\)$ \text{为常数时,时间复杂度为线性的} $\(O(n)\);
- 空间复杂度:内存仅需维持规模为 \(k\)$ \text{的辅助堆,空间复杂度为} $\(O(k) = O(1)\)。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2024 年 408 第 9 题 · 大根堆连续删除操作¶
题目
已知关键字序列 28, 22, 20, 19, 8, 12, 15, 5 是大根堆(最大堆),对该堆进行两次删除操作后,得到的新堆是( )。
A. 20, 19, 15, 12, 8, 5 B. 20, 19, 15, 5, 8, 12
C. 20, 19, 12, 15, 8, 5 D. 20, 19, 8, 12, 15, 5
【解析】¶
-
画出初始堆对应的完全二叉树: 初始堆元素总数 \(n = 8\),下标序列为:
A[1]=28, A[2]=22, A[3]=20, A[4]=19, A[5]=8, A[6]=12, A[7]=15, A[8]=5 -
第一次删除堆顶操作:
- 弹出堆顶 28;
- 将末尾元素 5(下标 8)移动至堆顶(下标 1),堆大小变为 \(n = 7\);
- 堆顶元素 5 执行向下筛选:
- 结点 1 的左右孩子分别为下标 2(值 22)与下标 3(值 20)。两孩子较大者为 22;
- 比较 \(5 < 22\),5 与 22 交换。此时 22 成为根,5 处于下标 2;
- 结点 2 的左右孩子分别为下标 4(值 19)与下标 5(值 8)。较大者为 19;
- 比较 \(5 < 19\),5 与 19 交换。此时 19 处于下标 2,5 处于下标 4;
- 结点 4 的左孩子下标为 \(2 \times 4 = 8 > 7\),已无孩子结点,筛选终止。
-
第一次删除后的序列(长度 7):
22, 19, 20, 5, 8, 12, 15。 -
第二次删除堆顶操作:
- 弹出堆顶 22;
- 将当前末尾元素 15(下标 7)移动至堆顶(下标 1),堆大小变为 \(n = 6\);
- 堆顶元素 15 执行向下筛选:
- 结点 1 的左右孩子分别为下标 2(值 19)与下标 3(值 20)。两孩子较大者为 20;
- 比较 \(15 < 20\),15 与 20 交换。此时 20 成为根,15 处于下标 3;
- 结点 3 的左孩子为下标 6(值 12),右孩子下标 \(2 \times 3 + 1 = 7 > 6\)(无右孩子);
- 比较 15 与其唯一孩子 12:由于 \(15 \ge 12\),满足大根堆条件,无需交换,筛选终止。
- 第二次删除后的堆序列(长度 6):
20, 19, 15, 5, 8, 12。
对应选项 B。
正确答案:B
【真题 2】2022 年 408 第 42 题 · 海量数据 Top-K 最小数算法设计¶
题目
现有 \(n\)(\(n > 100000\)$ \text{)个数保存在一维数组} $\(M\)$ \text{中,需要查找} $\(M\) 中最小的 10 个数,请回答下列问题。
(1) 设计一个完成上述查找任务的算法,要求平均情况下的比较次数尽可能少,简单描述其算法思想,不需要程序实现。
(2) 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
【解析】¶
- 算法选型分析:
- 若使用全局全排序(如快速排序或堆排序),时间复杂度为 \(O(n \log n)\),处理海量数据效率低下且做了大量无用功;
- 若使用简单选择排序进行 10 趟选择,比较次数约为 \(10n\)$ \text{,时间复杂度为} $\(O(n)\),但内部比较次数较多;
-
最佳方案为:维护容量为 \(k = 10\) 的大根堆。利用堆顶元素作为门槛,在常数时间内过滤绝大多数不合规元素。
-
问题 (1) 算法思想描述:
- 建立一个容量为 10 的大根堆 \(H\)$ \text{。初始时将数组} $\(M\)$ \text{的前 10 个元素建立大根堆(或将堆中 10 个元素初值置为该数据类型的最大值} $\(\text{MAX}\));
- 顺序遍历数组 \(M\)$ \text{中剩余的} $\(n - 10\)$ \text{个元素,设当前元素为} $\(x\):
- 将 \(x\) 与堆顶元素(即堆中当前 10 个数中的最大值)进行比较;
- 若 $$ \text{x < \text{堆顶元素}} $$,说明堆顶元素不可能属于全局最小的 10 个数,删除当前堆顶,将 \(x\) 放入堆顶,并调用向下调整(Sift-Down)恢复大根堆性质;
- 若 $$ \text{x \ge \text{堆顶元素}} $$,说明 \(x\) 不小于当前最小的 10 个数,直接舍弃;
-
当数组 \(M\)$ \text{中所有元素遍历完毕,堆} $\(H\)$ \text{中留存的 10 个元素即为数组} $\(M\) 中最小的 10 个数。
-
问题 (2) 复杂度分析:
- 时间复杂度:
- 建堆:对初始 10 个元素建堆时间为 \(O(k) = O(10)\);
- 扫描过滤:对后续 \(n - 10\)$ \text{个元素,每次仅需 1 次比较。由于数据规模} $\(n > 100000\)$ \text{,平均情况下只有极少数元素小于堆顶并触发堆调整;即使触发调整,容量为 10 的堆高度为} $\(\lfloor \log_2 10 \rfloor + 1 = 4\),向下调整至多比较 6 次(每层至多比较 2 次)。
- 总时间复杂度为 \(O(n \log k)\)$ \text{。因} $\(k = 10\)$ \text{为常数,平均时间复杂度为 } $\(O(n)\)。
- 空间复杂度:
- 算法仅需常数规模的辅助空间维持大小为 10 的大根堆,辅助空间复杂度为 \(O(1)\)$ \text{(或} $\(O(k)\))。
【真题 3】2021 年 408 第 11 题 · 大根堆动态插入构建¶
题目
将关键字 6, 9, 1, 5, 8, 4, 7 依次插入到初始为空的大根堆 \(H\)$ \text{中,得到的} $\(H\) 是( )。
A. 9, 8, 7, 6, 5, 4, 1 B. 9, 8, 7, 5, 6, 1, 4
C. 9, 8, 7, 5, 6, 4, 1 D. 9, 6, 7, 5, 8, 4, 1
【解析】¶
本题考查逐个元素动态插入堆的过程(新元素追加至数组末尾,随后沿双亲链执行向上筛选 Sift-Up):
1. 插入 6:堆为空,6 成为根结点。序列:[6];
2. 插入 9:
* 追加至末尾下标 2(6 的左孩子):[6, 9];
* 向上调整:双亲为 6,由于 \(9 > 6\),9 与 6 交换,9 到达根结点。序列:[9, 6];
3. 插入 1:
* 追加至末尾下标 3(9 的右孩子):[9, 6, 1];
* 向上调整:双亲为 9,由于 \(1 < 9\),无需调整。序列:[9, 6, 1];
4. 插入 5:
* 追加至末尾下标 4(6 的左孩子):[9, 6, 1, 5];
* 向上调整:双亲为 6,由于 \(5 < 6\),无需调整。序列:[9, 6, 1, 5];
5. 插入 8:
* 追加至末尾下标 5(6 的右孩子):[9, 6, 1, 5, 8];
* 向上调整:双亲为下标 2(值为 6)。由于 \(8 > 6\),8 与 6 交换,此时 8 位于下标 2,序列变为 [9, 8, 1, 5, 6];
* 继续向上考察:下标 2 的双亲为下标 1(值为 9),由于 \(8 < 9\),调整终止。序列:[9, 8, 1, 5, 6];
6. 插入 4:
* 追加至末尾下标 6(1 的左孩子):[9, 8, 1, 5, 6, 4];
* 向上调整:双亲为下标 3(值为 1)。由于 \(4 > 1\),4 与 1 交换,此时 4 位于下标 3,序列变为 [9, 8, 4, 5, 6, 1];
* 继续向上考察:下标 3 的双亲为下标 1(值为 9),由于 \(4 < 9\),调整终止。序列:[9, 8, 4, 5, 6, 1];
7. 插入 7:
* 追加至末尾下标 7(4 的右孩子):[9, 8, 4, 5, 6, 1, 7];
* 向上调整:双亲为下标 3(值为 4)。由于 \(7 > 4\),7 与 4 交换,此时 7 位于下标 3,序列变为 [9, 8, 7, 5, 6, 1, 4];
* 继续向上考察:下标 3 的双亲为下标 1(值为 9),由于 \(7 < 9\),调整终止。序列:[9, 8, 7, 5, 6, 1, 4]。
最终所得序列为:9, 8, 7, 5, 6, 1, 4。对应选项 B。
正确答案:B
【真题 4】2020 年 408 第 9 题 · 大根堆概念与结构性质辨析¶
题目
下列关于大根堆(至少含 2 个元素)的叙述中正确的是( )。
I. 可以将堆看成一棵完全二叉树;
II. 可采用顺序存储方式保存堆;
III. 可以将堆看成一棵二叉排序树;
IV. 堆中的次大值一定在根的下一层。
A. 仅 I, II B. 仅 II, III C. 仅 I, II, IV D. 仅 I, III, IV
【解析】¶
- 命题 I 正确:堆在逻辑结构上表现为一棵完全二叉树。除最后一层外其余层均填满,且最后一层的叶结点全部自左向右连续排列。
- 命题 II 正确:完全二叉树具备紧凑的拓扑特性,结点下标之间满足简单的代数对应关系(\(2i, 2i+1\)),顺序存储无内部空闲碎片,空间利用率为 100%,且寻址效率极高。
- 命题 III 错误:二叉排序树要求满足全局全序关系(左子树 \(<\)$ \text{根} $\(<\)$ \text{右子树),其中序遍历单调有序;而大根堆仅要求局部偏序(双亲} $\(\ge\) 孩子),对左右孩子之间的大小次序无任何规定,中序遍历无单调性。故堆不能视作二叉排序树。
- 命题 IV 正确:大根堆的子树亦为大根堆,根结点存储全局最大值。集合中的次大值必然在除根结点外的所有结点中取得。由于整棵树中其余所有结点均分别为左子树或右子树的后代,而子树的最大值必定是子树的根,因此全局次大值必定是左子树的根或右子树的根,即一定位于根结点的直接下一层(第 2 层,下标 2 或 3)。
综上所述,叙述正确的是 I、II、IV。
正确答案:C
【真题 5】2018 年 408 第 11 题 · 自底向上批量建堆状态演变¶
题目
在将数据序列 (6, 1, 5, 9, 8, 4, 7) 建成大根堆时,正确的序列变化过程是( )。
A. 6, 1, 7, 9, 8, 4, 5 \(\to\) 6, 9, 7, 1, 8, 4, 5 \(\to\) 9, 6, 7, 1, 8, 4, 5 \(\to\) 9, 8, 7, 1, 6, 4, 5
B. 6, 9, 5, 1, 8, 4, 7 \(\to\) 6, 9, 7, 1, 8, 4, 5 \(\to\) 9, 6, 7, 1, 8, 4, 5 \(\to\) 9, 8, 7, 1, 6, 4, 5
C. 6, 9, 5, 1, 8, 4, 7 \(\to\) 9, 6, 5, 1, 8, 4, 7 \(\to\) 9, 6, 7, 1, 8, 4, 5 \(\to\) 9, 8, 7, 1, 6, 4, 5
D. 6, 1, 7, 9, 8, 4, 5 \(\to\) 7, 1, 6, 9, 8, 4, 5 \(\to\) 7, 9, 6, 1, 8, 4, 5 \(\to\) 9, 7, 6, 1, 8, 4, 5 \(\to\) 9, 8, 6, 1, 7, 4, 5
【解析】¶
本题考查自底向上批量建堆算法(Floyd 建堆法):
序列元素总数 \(n = 7\),下标范围为 1~7。
最后一个非叶结点下标为 \(\lfloor n/2 \rfloor = \lfloor 7/2 \rfloor = 3\)。
建堆调整顺序严格为:结点 3 \(\to\)$ \text{结点 2} $\(\to\) 结点 1,逐一执行向下筛选。
初始完全二叉树状态:
A[1]=6, A[2]=1, A[3]=5, A[4]=9, A[5]=8, A[6]=4, A[7]=7
- 第一步:调整结点 3(值为 5):
- 结点 3 的左孩子为下标 6(值为 4),右孩子为下标 7(值为 7);
- 两孩子较大者为 7(下标 7);
- 比较 \(5 < 7\),交换 5 与 7。此时结点 3 值为 7,结点 7 值为 5;
-
序列变化为:
(6, 1, 7, 9, 8, 4, 5)。
(观察选项:B、C 项第一步直接调整结点 2,颠倒了自底向上的次序,直接排除 B、C)。 -
第二步:调整结点 2(值为 1):
- 结点 2 的左孩子为下标 4(值为 9),右孩子为下标 5(值为 8);
- 两孩子较大者为 9(下标 4);
- 比较 \(1 < 9\),交换 1 与 9。此时结点 2 值为 9,结点 4 值为 1;
-
序列变化为:
(6, 9, 7, 1, 8, 4, 5)。 -
第三步:调整结点 1(值为 6):
- 结点 1 的左孩子为下标 2(值为 9),右孩子为下标 3(值为 7);
- 两孩子较大者为 9(下标 2);
- 比较 \(6 < 9\),交换 6 与 9。此时根结点 1 变为 9,原 6 下沉至下标 2;
- 此时生成中间状态:
(9, 6, 7, 1, 8, 4, 5); - 考察处于下标 2 的元素 6,必须继续向下递归筛选:
- 其左右孩子为下标 4(值为 1)与下标 5(值为 8);
- 两孩子较大者为 8(下标 5);
- 比较 \(6 < 8\),再次交换 6 与 8。此时下标 2 值为 8,下标 5 值为 6;
- 调整完毕,最终序列变为:
(9, 8, 7, 1, 6, 4, 5)。
整个序列状态演进链条为:
6, 1, 7, 9, 8, 4, 5 \(\to\) 6, 9, 7, 1, 8, 4, 5 \(\to\) 9, 6, 7, 1, 8, 4, 5 \(\to\) 9, 8, 7, 1, 6, 4, 5。
完全符合选项 A。
正确答案:A
四、 核心解题套路与易错陷阱¶
1. 批量建堆与逐个插入建堆的算法逻辑混淆¶
考研试卷中建堆题型通常存在两种命题模式,解题策略截然不同: * 模式一:“将数据序列建成堆”(批量建堆): 采用 Floyd 自底向上筛选法。必须从下标 \(\lfloor n/2 \rfloor\) 开始倒序直至 1 调用向下调整(Sift-Down)。如 2018 年第 11 题。 * 模式二:“将关键字依次插入初始为空的堆”(动态插入): 采用连续追加与向上调整法。新元素依次放置在末尾,随后向上调整(Sift-Up)。如 2021 年第 11 题。 * 注意:同一组输入序列,通过上述两种方式构建出的最终堆序列通常不相同。审题时必须仔细看清是“序列建堆”还是“依次插入”。
2. Top-K 检索算法的堆型选取“逆向原则”¶
在设计或分析 Top-K 极值问题时,极易陷入直觉误区: * 求最小 \(k\)$ \text{个数:必须建立容量为} $\(k\)$ \text{的【大根堆】。利用大根堆堆顶保存这} $\(k\) 个数中的“最大值”作为门槛,一旦新元素比堆顶还小,即淘汰堆顶下沉新元素。 * 求最大 \(k\)$ \text{个数:必须建立容量为} $\(k\)$ \text{的【小根堆】。利用小根堆堆顶保存这} $\(k\) 个数中的“最小值”作为门槛,一旦新元素比堆顶还大,即淘汰堆顶下沉新元素。 * 常见误区:考生常误写为“求最小用小根堆”,若使用容量为 \(k\)$ \text{的小根堆求最小} $\(k\)$ \text{个数,堆顶保存的是当前集合的全局最小值,当遇到新元素时,无法判断新元素与集合内最大者(即第} $\(k\) 小数)的大小关系,必须遍历堆中所有元素,算法退化。
3. 堆排序中升降序与堆类型的“反向逻辑”¶
- 输出升序序列 \(\implies\) 必须建立大根堆: 堆顶最大值交换至末尾(\(A[n]\)),未排序区间缩小,重复操作使得数组自右向左逐步形成升序序列。
- 输出降序序列 \(\implies\) 必须建立小根堆: 堆顶最小值交换至末尾,重复操作使得数组自右向左逐步形成降序序列。
4. 堆中特定位序元素的候选范围陷阱¶
在选择题中常考查某些特定序位元素的位置约束: * 最大值(大根堆):唯一确定在根结点(第 1 层)。 * 次大值(大根堆):必然在根的下一层(第 2 层,左孩子或右孩子之一)。 * 第三大值(大根堆):可能在第 2 层(根的另一个孩子),亦可能在第 3 层(次大值的左右孩子之一)。绝不可能在第 4 层或更深层。 * 最小值(大根堆):必然位于叶结点集合中(下标范围 \(\lfloor n/2 \rfloor + 1 \sim n\)),但具体在哪个叶结点无法预知。
五、 考点速记清单¶
- 结构本质:堆在逻辑上是完全二叉树,在物理上采用一维数组顺序存储,无存储空隙,通过算术运算(\(2i, 2i+1, \lfloor i/2 \rfloor\))实现常数时间父子寻址。
- 偏序特征:大根堆双亲 \(\ge\)$ \text{孩子;小根堆双亲} $\(\le\) 孩子。堆仅具备父子偏序,左右孩子无大小次序约束,堆的中序遍历无单调性,不可将堆看作二叉排序树。
- 两项调整机制:
- 插入操作:追加末尾 \(\to\)$ \text{向上调整(Sift-Up),复杂度} $\(O(\log n)\);
- 删除操作:堆顶与末尾对调 \(\to\)$ \text{堆长减 1} $\(\to\)$ \text{堆顶向下调整(Sift-Down),复杂度} $\(O(\log n)\)。
- 建堆代价:
- 自底向上批量建堆(Floyd 算法)时间复杂度为严格的 \(O(n)\)(利用错位相减法求和);
- 逐个插入建堆时间复杂度为 \(O(n \log n)\)。
- 极值位置分布(大根堆):
- 最大值:第 1 层(根);
- 次大值:第 2 层(两节点之一);
- 第三大值:第 2 层或第 3 层(至多 6 个可能位置);
- 最小值:必定属于叶结点(下标 \(\lfloor n/2 \rfloor + 1 \sim n\))。
- Top-K 选型准则:海量数据求最小 \(k\)$ \text{个数维护大根堆;求最大} $\(k\)$ \text{个数维护小根堆。时间复杂度为} $\(O(n \log k)\)$ \text{,空间复杂度为} $\(O(k)\)。
- 堆排序准则:升序建大根堆,降序建小根堆;时间复杂度恒为 \(O(n \log n)\)$ \text{,空间复杂度} $\(O(1)\),为不稳定排序。