入门：完全二叉树、堆序性与数组表示
基于通用数据结构概念 · 核于 2026-07
速查
- 定义：堆是一棵完全二叉树，且满足堆序性——每个节点的值都 ≤（小根堆）或 ≥（大根堆）其子节点的值。
- 完全二叉树：除最后一层外每层都填满，最后一层节点从左到右连续——这个「紧致」形状是堆能用数组无缝表示的前提。
- 大根堆 / 小根堆：大根堆父 ≥ 子（堆顶是最大值）；小根堆父 ≤ 子（堆顶是最小值）。注意堆序性是父子关系，不要求兄弟之间有序。
- 数组表示：把完全二叉树按层序映射到数组（下标 0 是根）。父子下标：父
(i-1)/2（整除）、左子2i+1、右子2i+2——都是 O(1) 算术运算，无需存指针。 - 为何 O(1) 父子访问：完全二叉树的「每层填满 + 末层左对齐」让节点编号与数组下标一一对应，父子关系是确定的算术公式，不依赖树的实际形状。
- 核心复杂度：取堆顶（极值）O(1)；插入（sift up）O(log n)；删除堆顶（sift down）O(log n)；建堆 O(n)（Floyd）；查任意值 O(n)（中间无序）。
- 堆 vs BST：堆只保证根是极值（部分序），BST 保证中序遍历有序（全序）。堆取最值 O(1)、查任意值 O(n)；BST 取最值 O(log n)、查任意值 O(log n)——选型看「要极值还是要全序」。
- 堆不关心全序：堆里同一层的节点、左右兄弟之间都没有大小约束，只约束父子——所以中序遍历堆得不到有序序列。
- 高度：n 个节点的完全二叉树高度为 ⌈log₂(n+1)⌉ - 1 ≈ log₂n，所以 sift up/down 最多走树高步，即 O(log n)。
- JS 无原生堆：JS 标准库没有 Heap 类，需手写（基于数组的 sift up/down）或用第三方库（如
heap-js）；Java 有PriorityQueue、C++ 有std::priority_queue、Python 有heapq。 - 进阶顺序：堆的核心操作 → 堆的工程应用 → 参考。
一、堆是什么：完全二叉树 + 堆序性
堆是两个性质的叠加：
- 完全二叉树（结构性质）：除最后一层外，每层都被完全填满；最后一层的节点从左到右连续排列，中间不留空。这个「紧致」形状保证了树高最小（⌈log₂n⌉），也是它能用数组无缝表示的前提。
- 堆序性（值性质）：每个节点的值都 ≤ 或 ≥ 其子节点。具体分两种：
- 大根堆（max-heap）：父节点 ≥ 子节点 → 堆顶是整堆的最大值。
- 小根堆（min-heap）：父节点 ≤ 子节点 → 堆顶是整堆的最小值。
大根堆示例 小根堆示例
9 1
/ \ / \
8 7 3 2
/ \ / / \ /
5 4 6 7 6 4关键：堆序性只约束「父子」，不约束「兄弟」。上面大根堆里 8 与 7（兄弟）谁大都行，5 与 4、6 之间也无序——只要每个父节点比自己的子节点大即可。这正是堆「只管根极值、不管全序」的根源。
二、数组表示：完全二叉树的天然映射
完全二叉树的「每层填满 + 末层左对齐」让它能按层序无缝映射到数组，且父子下标有确定的算术公式。约定根在下标 0：
下标 i 的节点：
父节点下标 = (i - 1) / 2 （整除，向下取整）
左子节点下标 = 2 * i + 1
右子节点下标 = 2 * i + 2
示例（大根堆 [9, 8, 7, 5, 4, 6]）：
下标: 0 1 2 3 4 5
值: 9 8 7 5 4 6
根 9 (下标0)
左子 8 (下标 2*0+1=1)
右子 7 (下标 2*0+2=2)
节点 8 (下标1) 的父 = (1-1)/2 = 0 ✓
节点 7 (下标2) 的父 = (2-1)/2 = 0 ✓ (整除)为什么这套映射是 O(1)
父子下标关系是纯算术运算（乘 2、加 1、除 2），不依赖树的实际形状、不需要遍历、不存指针——CPU 一个时钟周期就算完。这就是堆「数组实现、无指针开销」的原因：
- 省内存：每个节点只存值，不存左右指针（BST 链式实现每个节点要 2 个指针）。
- 缓存友好：数组连续存放，sift up/down 沿路径访问时命中缓存行。
- 父子访问 O(1)：
parent = (i-1) >> 1、left = (i<<1) + 1、right = (i<<1) + 2，位运算更快。
前提是「完全二叉树」：如果树中间有空缺（普通二叉树），下标公式就失效了——因为「下标 2i+1/2i+2」隐含了「第 i 个节点的子节点一定紧挨在它后面」这一完全性假设。所以只有完全二叉树才能这样映射，这也是堆必须是完全二叉树的工程理由。
三、大根堆 vs 小根堆：选哪个
| 维度 | 大根堆（max-heap） | 小根堆（min-heap） |
|---|---|---|
| 堆序性 | 父 ≥ 子 | 父 ≤ 子 |
| 堆顶 | 最大值 | 最小值 |
| 典型场景 | 取前 K 大的辅助、堆排序（升序） | 优先队列、Top-K 前 K 大、Dijkstra |
Java PriorityQueue | 需传反转比较器 | 默认 |
记忆：「要最小用小根堆，要最大用大根堆」——堆顶直接给你要的极值。一个反直觉但高频的技巧：求前 K 大元素用小根堆（维护大小为 K 的小根堆，新元素比堆顶大就替换堆顶，最后堆里就是前 K 大）——详见堆的工程应用。
四、堆与二叉搜索树（BST）的区别
堆和 BST 都是二叉树，但约束完全不同：
| 维度 | 堆 | 二叉搜索树（BST） |
|---|---|---|
| 结构约束 | 完全二叉树（形状固定） | 任意形状（左 < 根 < 右） |
| 值约束 | 父子：父 ≥/≤ 子（部分序） | 全序：左子树 < 根 < 右子树 |
| 堆顶 / 根 | 堆顶是极值（最大或最小） | 根是「中间值」，非极值 |
| 取最值 | O(1)（堆顶就是） | O(log n)（走到最左/最右） |
| 查任意值 | O(n)（中间无序，线性扫描） | O(log n)（有序可二分） |
| 插入/删除 | O(log n)（sift up/down） | O(log n)（平均）/ O(n)（最坏退化成链） |
| 中序遍历 | 无序（不保证全序） | 有序（升序序列） |
一句话：堆只管「根是极值」（取最值快，查任意值慢）；BST 管「全序」（查任意值快，取极值要走到端点）。所以：
- 要动态取极值、做优先队列 → 堆（取最值 O(1) 是核心优势）。
- 要频繁按值查找、要有序遍历 → BST（平衡树 / 红黑树）。
堆「牺牲全序换 O(1) 极值」的设计，正是为优先队列这类「只关心谁该最先出队」的场景量身定做的。
五、堆的高度：为什么操作是 O(log n)
n 个节点的完全二叉树，每层节点数翻倍（第 0 层 1 个、第 1 层 2 个、第 2 层 4 个……），所以高度 h 满足：
2^0 + 2^1 + ... + 2^(h-1) + 最后不满一层 = n
即 2^h - 1 ≤ n ≤ 2^(h+1) - 1
解得 h ≈ ⌊log₂n⌋sift up（从尾部往上走）和 sift down（从堆顶往下走）每步移动一层，最多走 h 步，所以都是 O(log n)。这也是「完全二叉树高度最小」的价值——同样的 n 个节点，链状树高度是 O(n)，完全二叉树是 O(log n)，操作快得多。
六、JS 无原生堆怎么办
主流语言的堆支持差异很大：
| 语言 | 堆实现 | 备注 |
|---|---|---|
| Java | java.util.PriorityQueue | 默认小根堆，传 Comparator.reverseOrder() 变大根堆 |
| C++ | std::priority_queue | 默认大根堆，配 greater<T> 变小根堆；还有 std::make_heap 系列操作原数组 |
| Python | heapq 模块 | 默认小根堆，操作 list；大根堆用取负技巧 |
| Go | container/heap | 接口式，需自己实现 Heap 接口 |
| JavaScript | 无原生 | 需手写（基于数组的 sift up/down，见堆的核心操作）或用第三方库（如 heap-js） |
JS 手写堆是面试常考题——核心就是下面两个操作（sift up / sift down），掌握了就能造出一个完整的小根堆。这也是为什么本叶在参考里给出完整的代码模板。
下一步
理解了堆的定义、数组表示与父子下标后，下一步是堆的两个核心操作——**sift up（插入上浮）**与 sift down（删除堆顶下沉），它们是所有堆操作的基石，见堆的核心操作。