《Hello 算法》堆章节习题精讲：入堆调整、小顶堆合法性检查与 Top-k / 第 k 大元素的堆解法

《Hello 算法》的 堆章节习题（中文版） 与 英文版习题 围绕堆的核心操作设计了 3 道概念自测题与 1 道编程练习：数字入堆后的向上调整、小顶堆父子关系合法性检查、用固定容量小顶堆维护数据流 Top-k，以及求数组中第 k 大元素。本文以这些习题为主体，逐一给出带索引推演的分步解答，并结合仓库源码（大顶堆实现、Top-k 堆实现）讲清每个操作背后的堆化原理与终止条件，帮你把"堆的数组表示、上滤与下滤、Top-k 堆维护"这些点彻底打通。

前置基础：用数组存堆时，父子节点的索引公式

习题大量使用"索引"描述父子关系，因此先统一约定。堆以"层序遍历"顺序存放在数组中：根节点下标为 0，对下标为 $i$ 的节点：

• 父节点下标：$\lfloor (i-1)/2 \rfloor$；
• 左孩子下标：$2i+1$；
• 右孩子下标：$2i+2$。

这与仓库中的手写堆实现完全一致。以 codes/c/chapter_heap/my_heap.c 为例，其 left()、right()、parent() 正是这三个公式：

• left() 返回 2 * i + 1；
• right() 返回 2 * i + 2；
• parent() 返回 (i - 1) / 2（整型除法即向下取整）。

注意边界：当孩子下标大于等于数组长度时，该孩子不存在（数组只存到最后一层实际元素为止）。

练习 1：向大顶堆 [9, 7, 8, 3, 5] 插入 10 —— 模拟向上堆化

题目要求

数组 [9, 7, 8, 3, 5] 表示一个大顶堆（大顶堆要求每个父节点不小于其孩子）。现在将数字 10 入堆，要求回答三个问题：

1. 先把 10 追加到数组末尾，它的父节点值是多少？
2. 从新节点开始向上堆化，写出每次交换后的数组；
3. 最终堆顶元素是什么？一共交换了几次？

分步推演

初始数组下标与值的映射为：

下标	0	1	2	3	4
值	9	7	8	3	5

第 1 步：追加 10。 数组变为 [9, 7, 8, 3, 5, 10]，10 的下标为 5。按父节点公式，其父节点下标为：

$$\lfloor (5-1)/2 \rfloor = \lfloor 4/2 \rfloor = 2$$

下标 2 处存放的值为 8。因此问题 1 的答案是：父节点值为 8。

第 2 步：向上堆化（逐次比较并交换）。 大顶堆要求父不小于子，现在 10 > 8，违反规则：

• 第一次交换：交换下标 2 与下标 5 的元素（8 与 10 互换），数组变为 [9, 7, 10, 3, 5, 8]；
• 此时 10 位于下标 2，其父节点下标为 $\lfloor (2-1)/2 \rfloor = 0$，值为 9。10 > 9，仍违反规则，进行第二次交换，数组变为 [10, 7, 9, 3, 5, 8]；
• 此时 10 已到达根节点（下标 0），不再有父节点，堆化结束。

第 3 步：结论。 最终堆顶元素为 10，共交换 2 次。可验证最终堆 [10, 7, 9, 3, 5, 8] 满足大顶堆性质：10 ≥ 7、10 ≥ 9，7 ≥ 3、7 ≥ 5，9 ≥ 8。

对应的源码实现：siftUp（从底至顶堆化）

这一过程正是 codes/c/chapter_heap/my_heap.c 中 siftUp 的逻辑。元素入堆时（push）先把新元素追加到数组末尾，再以它为新节点调用 siftUp 向上修复：

• 计算当前节点 $i$ 的父节点下标 $p = (i-1)/2$；
• 终止条件有两个：要么 $p < 0$（已经越过根节点，即新元素到达堆顶）；要么 data[i] <= data[p]（父节点已经不小于当前节点，满足大顶堆规则，无须继续调整）；
• 若两者都不满足，说明 data[i] > data[p]，交换两者，令 i = p 后进入下一轮循环。

正是这个"每轮最多交换一次并上升一层"的过程，决定了入堆操作的时间复杂度为 $O(\log n)$（$n$ 为堆中元素个数）。对比上面的手工推演可以看出：练习 1 手工模拟的两轮交换，恰好对应 siftUp 循环体的两次迭代。

练习 2：检查小顶堆 [1, 4, 3, 7, 6, 2] 的父子关系 —— 逐层合法性校验

题目要求

数组 [1, 4, 3, 7, 6, 2] 表示一棵完全二叉树。小顶堆要求每个父节点都不大于它的孩子。已知对下标 $i$，左、右孩子下标分别为 $2i+1$、$2i+2$。请回答：

1. 下标 2 的孩子的下标和值分别是什么？
2. 下标 2 处节点的值为 3，它是否与孩子节点违反小顶堆规则？若违反，应交换哪两个元素？
3. 若违反规则，写出交换后的数组；否则说明无须交换。最后检查其余全部父子关系。

分步推演

数组下标与值：0→1、1→4、2→3、3→7、4→6、5→2，数组长度 6。

问题 1： 下标 2 的左孩子下标为 $2 \times 2 + 1 = 5$，值 2；右孩子下标为 $2 \times 2 + 2 = 6$，但数组有效下标为 0～5，因此右孩子不存在。

问题 2： 父节点值 3 大于唯一孩子值 2，违反小顶堆规则（小顶堆要求父 ≤ 子）。应交换下标 2 与下标 5 的元素，即 3 与 2 互换。

问题 3： 交换后得到 [1, 4, 2, 7, 6, 3]。逐一检查全部父子关系：

• 下标 0（值 1）：孩子为下标 1（值 4）、下标 2（值 2），满足 $1 \le 4$、$1 \le 2$；
• 下标 1（值 4）：孩子为下标 3（值 7）、下标 4（值 6），满足 $4 \le 7$、$4 \le 6$；
• 下标 2（值 2）：孩子为下标 5（值 3），满足 $2 \le 3$。

所有父节点都不大于各自孩子，此时数组满足小顶堆规则。

与源码的呼应：从"违反处"向下堆化

此题本质是在一个小顶堆中定位并修复一处局部违规。若把下标 2 视为待修复的起点，则修复动作对应 codes/c/chapter_heap/my_heap.c 中的 siftDown（从顶至底堆化）：在节点 $i$、左孩子 $l$、右孩子 $r$ 三者中找出最小者（小顶堆视角，练习中即孩子 2 小于父节点 3，取值为 2 的孩子）；若最小者不是 $i$，则交换 $i$ 与该孩子，并将 $i$ 下移后继续循环。

需要特别说明一个易错点：本题修复只需一次交换，是因为交换后节点 2 的新值 2 恰好小于其唯一孩子 3。若交换后新值仍大于某个孩子，就必须继续向下堆化多轮，这正是 siftDown 循环存在的意义——一次"违规交换"并不保证整棵子树立即合法，需要沿路径持续下滤直至满足条件。

练习 3：用小顶堆保留数据流 [4, 1, 7, 3, 8] 中最大的 3 个数 —— 固定容量堆的 Top-k 演练

题目要求

维护一个大小不超过 3 的小顶堆：先把前 3 个数依次放入堆；堆满后每读入一个新数，若它大于堆顶，就删除堆顶并放入新数，否则堆保持不变。要求写出每次读入后堆中保留的数字（以集合形式给出，不要求堆内排列顺序）与堆顶。

逐步过程与答案

读入数字	堆中保留的数字（集合）	堆顶	说明
4	{4}	4	堆未满，直接入堆
1	{1, 4}	1	堆未满，直接入堆
7	{1, 4, 7}	1	堆满（容量 3），新数先不入堆
3	{3, 4, 7}	3	3 > 堆顶 1，弹出 1、插入 3
8	{4, 7, 8}	4	8 > 堆顶 3，弹出 3、插入 8

关键不变式：堆一旦满容量，堆顶就是当前保留数字中最小者；只有当新数字大于堆顶（即比当前"第 3 大"更值得保留）时才发生替换。最终堆中保留的 {4, 7, 8} 恰好是数据流中最大的 3 个数（排序后为 8、7、4），堆顶 4 就是当前最大的 3 个数里的最小者。

这个维护规则可以简单概括为：小顶堆固定容量 k，堆顶负责"淘汰"当前最不值得保留的最小值，新元素只有胜过堆顶才能入局。

与正文 Top-k 章节的对应关系

这道概念题的流程就是《Hello 算法》Top-k 问题章节（方法 3：堆）的精确复刻：

1. 初始化一个小顶堆，堆顶元素最小；
2. 先将数组前 $k$ 个元素依次入堆；
3. 从第 $k+1$ 个元素起，若当前元素大于堆顶，则移除堆顶并插入当前元素；
4. 遍历结束后，堆中即为最大的 $k$ 个元素。

该方案天然适合动态数据流场景：新数据不断到达时，只需持续维护堆内元素，即可动态更新最大的 $k$ 个元素，这也是它与"先排序再取前 k 个""k 轮遍历挑选"两种方案相比的核心优势。仓库在多种语言下均有该算法的可运行实现，例如：

• codes/python/chapter_heap/top_k.py：top_k_heap(nums, k) 完整实现，驱动代码用 nums = [1, 7, 6, 3, 2]、k = 3 验证；
• codes/c/chapter_heap/top_k.c、codes/java/chapter_heap/top_k.java 等其他语言版本，可在对应目录中查看。

编程练习：用大小不超过 k 的小顶堆求数组中第 k 大元素

题目要求

给定整数数组 nums 与整数 $k$（$1 \le k \le n$，$n$ 为数组长度），把数组按从大到小排列后，返回第 $k$ 个位置上的元素。重复元素须分别计数。例如 [5, 5, 2] 的第 2 大元素仍是 5。要求使用一个大小不超过 $k$ 的小顶堆完成。

该题即经典题目"数组中的第 K 个最大元素"。英文版习题页内嵌了对应 LeetCode 题目的跳转按钮；需要特别提醒的是，该题常见的官方题解采用快速排序 / 快速选择思路（并未使用堆），而本练习依据书中的堆章节要求，应严格用"大小不超过 $k$ 的小顶堆"完成。

关键思路（即文档给出的三条提示）

1. 第 k 大元素 = 最大的 k 个数中最小的那个。这是本题的核心观察，也正是把"小顶堆堆顶"作为答案的原因；
2. 每个数先入小顶堆，堆大小一旦超过 $k$ 就弹出堆顶（最小值）。通过"入堆—超容弹出"持续淘汰已扫描数据中最小的元素，保证堆内永远只保留目前最大的 $k$ 个；
3. 遍历结束时，堆中保留最大的 $k$ 个数，堆顶就是第 k 大元素。

因为重复元素被分别计数，这个流程对重复值天然正确：以 [5, 5, 2]、$k=2$ 为例，两个 5 会作为两个独立元素入堆，堆中保留 {5, 5}，堆顶（第 2 大）仍为 5。

与源码逐行对应

仓库中 codes/python/chapter_heap/top_k.py 的 top_k_heap 与上述思路完全一致：

def top_k_heap(nums: list[int], k: int) -> list[int]:
    # 初始化小顶堆
    heap = []
    # 将数组的前 k 个元素入堆
    for i in range(k):
        heapq.heappush(heap, nums[i])
    # 从第 k+1 个元素开始，保持堆的长度为 k
    for i in range(k, len(nums)):
        # 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if nums[i] > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, nums[i])
    return heap

实现要点：Python 的 heapq 默认为小顶堆，heap[0] 即堆顶最小值。前 $k$ 个元素直接入堆建立初始候选集；此后每个元素只与堆顶比较，大于堆顶才执行"弹出最小、压入更大"，从而将堆的容量始终约束在 $k$。

复杂度与运行前提

从 Top-k 章节正文 的分析可知：全程共 $n$ 轮入堆/出堆操作，堆的最大长度为 $k$，故时间复杂度为 $O(n \log k)$；当 $k$ 较小时复杂度趋近 $O(n)$，当 $k$ 较大时也不超过 $O(n \log n)$。空间复杂度为 $O(k)$（堆本身）。相比"排序后取前 k 个"的 $O(n \log n)$ 与"k 轮遍历挑选"的 $O(nk)$，堆方案在 $k$ 与 $n$ 同数量级之外的大多数场景下更优，且对数据流场景可在线维护。运行示例：进入 codes/python 目录执行 python chapter_heap/top_k.py，即可看到 nums = [1, 7, 6, 3, 2]、$k=3$ 时输出的最大 3 个元素及其堆结构打印。

小结

三道概念题与一道编程题串起了堆操作的三条主线：

• 向上堆化（siftUp）：入堆 = 追加到末尾 + 逐层与父节点比较交换，用于"插入"场景，见 my_heap.c 中 siftUp；
• 向下堆化（siftDown）：在父子关系中定位违规点后沿子树下滤，既用于"删除堆顶"，也用于自建堆与合法性修复，见 my_heap.c 中 siftDown；
• 固定容量小顶堆：堆顶为当前最大值集合中的最小值，是 Top-k 问题与"第 k 大元素"的统一点。

建议按"先独立推演 → 再对照文中索引表 → 最后运行仓库代码验证"的顺序完成本组练习。若想进一步掌握堆的底层原理，可继续阅读仓库中的 堆章节正文、堆的构建章节 与 Top-k 章节（对应英文版为 en/docs/chapter_heap），并对照同一章节下 C / C++ / Java / Python / Go / Rust / JS / TS / Swift / Ruby / Kotlin / Dart 等十余种语言的 堆实现代码 逐一运行体会。