知识点深化 · 数据结构 · 堆与优先队列
堆与优先队列：大顶堆小顶堆、堆排序、TopK
堆是一棵完全二叉树，且满足"父节点总 ≥（或≤）孩子"。它能 O(log n) 地取出最值，是优先队列、TopK、任务调度的底层。这一页把大顶堆/小顶堆的数组表示、上浮下沉、堆排序和 TopK 讲透。
① 小白第一课怎么学（4 步走，约 60 分钟）
别急着背代码，先按这四步建立直觉：
1看图建立直觉（10 分钟）
读②③：想象堆是"最值永远在根"的完全二叉树。
2记数组表示（15 分钟）
读④：i 的孩子在 2i+1/2i+2，上浮下沉。
3手推堆操作（20 分钟）
精读⑤：插入上浮、删根下沉、堆排序。
4刷题纠错（15 分钟）
做⑦⑩，错题回⑥。
本课小目标学完你要能：① 说出大顶堆/小顶堆定义；② 用数组父子下标公式；③ 解释 TopK 为什么用小顶堆。
② 一图看懂：堆与优先队列全地图
读法：中心是堆，上是大顶/小顶，右是数组表示，下是应用 TopK 与易错。
③ 本质直觉：堆就是"最值永远蹲在根上"的完全二叉树
堆的两条铁律：① 它是完全二叉树（每层填满，最后一层靠左）；② 大顶堆每个父节点 ≥ 两个孩子，小顶堆每个父节点 ≤ 孩子。所以根永远是最值。
用数组存：因为完全二叉树形状规整，直接存在数组里。下标 i 的左孩子在 2i+1，右孩子在 2i+2，父节点在 (i-1)/2。
两个核心动作：新元素加到末尾，若比父大（大顶堆）就上浮 swap；删根时把末尾元素搬到根，再一路下沉和较大的孩子交换。都是 O(log n)。
为什么 TopK 用小顶堆要找最大的 K 个数，维护一个大小为 K 的小顶堆：堆顶是当前 K 个里最小的。新数来了比堆顶大就替换堆顶再下沉——最后堆里就是最大 K 个。时间 O(n log K)，比全排序 O(n log n) 省。
④ 完整体系与对比表
核心操作复杂度
| 操作 | 说明 | 复杂度 |
|---|
| 建堆 | 从最后一个非叶子节点下沉 | O(n) |
| 插入 | 放末尾再上浮 | O(log n) |
| 取堆顶 | 直接 arr[0] | O(1) |
| 删堆顶 | 末尾换根再下沉 | O(log n) |
| 堆排序 | 反复取堆顶 | O(n log n) |
父子下标公式
数组下标关系（0 起）左孩子 = 2i+1，右孩子 = 2i+2，父 = (i-1)/2
堆排序三步走
① 建大顶堆：从最后一个非叶子节点 (n/2−1) 往前逐个下沉；② 交换：把堆顶（最大值）和末尾元素交换；③ 下沉：堆大小减 1，对新堆顶下沉。重复②③直到堆空。结果从小到大排序。
⑤ 用法场景与典型例题
例1（数组对应）堆数组 [9,6,8,3,2]，下标 1 的孩子是哪两个？
2i+1 和 2i+2。
i=1：左=2×1+1=2（值8），右=2×1+2=3（值3）。即节点 6 的孩子是 8 和 3。
例2（TopK）从 100 万个数找最大 100 个，用什么堆？
大小 K=100 的小顶堆。
维护小顶堆，堆顶是当前 100 个里最小的。遍历每个数：比堆顶大就替换并下沉。O(n log 100)。答案：小顶堆（找最大 K 用小顶堆）。
例3（堆排序）大顶堆反复取堆顶得到什么序？
堆顶是最大值，换到末尾。
每次把最大值换到数组末尾，剩余部分重新堆化。最终数组从前往后是升序。
做题心法找最大 K 用小顶堆，找最小 K 用大顶堆——和直觉相反，记"堆顶是要被淘汰的那个"。
⑥ 高频错误诊断（4 条）
错误1：TopK 堆选反找最大 K 要用小顶堆（堆顶最小，方便淘汰），不是大顶堆。
错误2：上浮下沉方向搞反大顶堆：孩子比父大才上浮/下沉交换；小顶堆相反。别把大小关系写反。
错误3：建堆从根开始建堆要从最后一个非叶子节点往前下沉，从根开始会多做无用功。
错误4：以为堆是有序数组堆只保证父子关系，兄弟之间无序，不是排序数组。
⑦ 考点真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 堆性质 | 问根是什么 | 大顶堆根最大，小顶堆根最小 |
| 下标公式 | i 的孩子位置 | 2i+1 / 2i+2 |
| TopK | 找最大 K 用什么堆 | 小顶堆 O(n log K) |
| 堆排序 | 复杂度/结果 | O(n log n)，升序 |
真题基础1. 大顶堆的根节点存储的是？
真题中档2. 数组下标 i 的左孩子下标是（0 起始）？
真题中档3. 从海量数据中求最大的 K 个数，应维护？
真题拔高4. 堆排序的时间复杂度是？
⑧ 必背知识点卡
大顶堆：父≥子，根最大 升序堆排
小顶堆：父≤子，根最小 TopK
下标：左 2i+1，右 2i+2，父 (i-1)/2
插入：末尾加，比父大上浮 O(log n)
删顶：末尾换根，下沉 O(log n)
建堆：从最后非叶子节点下沉 O(n)
TopK：找最大 K 用小顶堆 O(n log K)
⑨ 应用输出：设计一个任务优先级调度器
场景：操作系统有多个任务按优先级执行，每次选优先级最高的运行。
① 选型：优先队列底层用大顶堆，优先级最高的任务永远在堆顶。
② 新任务到达：插入堆，上浮到正确位置 O(log n)。
③ 调度：取堆顶执行最高优先级任务，删除堆顶（末尾换根下沉）O(log n)。
④ 动态改优先级：更新节点值后重新上浮/下沉。
⑤ 效果：不用全排序，O(log n) 就能拿到最值。
口述思路合上书说："优先级调度就是大顶堆，堆顶永远是最高优先级任务。"
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
▍中档 6 题
中档7找最小 K 个数用什么堆？
大顶堆（堆顶是 K 个里最大的，方便淘汰）。
中档8建堆时间复杂度？
O(n)，不是 O(n log n)。
中档9堆排序为什么不稳定？
交换跨度大，相等元素相对顺序可能变。
中档10优先队列底层通常是什么？
堆（Java PriorityQueue 是小顶堆）。
中档11下沉时大顶堆要和哪个孩子交换？
两个孩子中较大的那个。
中档12堆适合频繁取最值吗？
适合，取堆顶 O(1)，调整 O(log n)。
▍拔高 6 题
拔高13为什么建堆是 O(n) 而不是 O(n log n)？
大部分节点在底层下沉路径短，总和收敛于 O(n)。
拔高14数据流中位数怎么求？
两个堆：大顶堆存较小半、小顶堆存较大半，动态平衡。
拔高15堆和 BST 的区别？
堆只要父子有序，取最值 O(1)；BST 全序但插入 O(log n) 且结构可能歪。
拔高16为什么 TopK 用堆而不是全排序？
只关心 K 个最值，O(n log K) 远小于 O(n log n)。
拔高17下沉 vs 上浮哪个在建堆用？
建堆用下沉（从后往前），插入用上浮。
拔高18堆排序空间复杂度？
原地 O(1)，但不稳定。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 堆是完全二叉树，父子定大小。② 左 2i+1 右 2i+2，插入上浮删顶下沉。③ 找最大 K 用小顶堆，建堆 O(n) 排 O(n log n)。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画堆数组对应图 | 父子下标算对 |
| 第 2 天 | 背操作表 + 基础 1-6 | 复杂度全对 |
| 第 3 天 | 做中档 7-12，手写下沉步骤 | 方向不反 |
| 第 4 天 | 做拔高 13-18，推中位数双堆 | 能讲清平衡 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述口诀，默写 TopK 思路 | 不看资料全默对 |
← 返回软件技术总览