Appearance
堆的原理与实现
数组能 O(1) 访问任意元素，但找最大值需要 O(n)。排序数组能 O(1) 找最大值，但插入需要 O(n)。有没有一种数据结构，既能快速找最值，又能快速插入？
答案是堆（Heap）。
堆是一种特殊的完全二叉树，它能在 O(log n) 时间内完成插入和删除最值操作，同时保证 O(1) 时间获取最值。这种平衡的性能使堆成为实现优先队列的首选数据结构。
什么是堆？
堆有一个精确的定义：
堆是一棵完全二叉树，并且满足堆序性质：每个节点的值都大于等于（或小于等于）其子节点的值。
拆解这个定义：
完全二叉树：除了最后一层，每层都是满的，最后一层从左到右连续填充。
完全二叉树 ✓ 非完全二叉树 ✗
1 1
/ \ / \
2 3 2 3
/ \ /
4 5 4堆序性质：父子节点之间有大小约束。
根据约束方向，堆分为两种：
最大堆 (Max Heap)
父节点 ≥ 子节点，根节点是最大值。
90 ← 最大值在根
/ \
80 70
/ \ / \
50 60 65 35
满足：90 ≥ 80, 90 ≥ 70
80 ≥ 50, 80 ≥ 60
70 ≥ 65, 70 ≥ 35最小堆 (Min Heap)
父节点 ≤ 子节点，根节点是最小值。
10 ← 最小值在根
/ \
20 15
/ \ / \
30 25 50 20
满足：10 ≤ 20, 10 ≤ 15
20 ≤ 30, 20 ≤ 25
15 ≤ 50, 15 ≤ 20重要区分：堆只保证父子关系，不保证兄弟之间的顺序。
这两棵都是合法的最大堆：
90 90
/ \ / \
80 70 70 80 ← 左右子交换，仍是堆
/ \ / \
50 60 60 50这与二叉搜索树（BST）不同——BST 要求左 < 根 < 右，堆不要求。
为什么用数组存储？
完全二叉树有一个完美的性质：可以用数组紧凑存储，无需指针。
存储映射：
树形结构： 数组表示：
90[0] index: 0 1 2 3 4 5 6
/ \ value: 90 80 70 50 60 65 35
80[1] 70[2]
/ \ / \
50[3] 60[4] 65[5] 35[6]按层序（从上到下、从左到右）把节点放入数组，完全二叉树的每个位置都有节点，不会浪费空间。
索引关系（0-based）：
| 关系 | 公式 | 示例 |
|---|---|---|
| 父节点 | Math.floor((i - 1) / 2) | parent(3) = 1 |
| 左子节点 | 2 * i + 1 | left(1) = 3 |
| 右子节点 | 2 * i + 2 | right(1) = 4 |
javascript
function parent(i) {
return Math.floor((i - 1) / 2);
}
function leftChild(i) {
return 2 * i + 1;
}
function rightChild(i) {
return 2 * i + 2;
}验证：
索引 4（值 60）：
- 父节点：(4-1)/2 = 1（值 80）✓
- 左子：2*4+1 = 9（超出数组，无左子）✓
索引 1（值 80）：
- 父节点：(1-1)/2 = 0（值 90）✓
- 左子：2*1+1 = 3（值 50）✓
- 右子：2*1+2 = 4（值 60）✓为什么这个公式成立？
完全二叉树第 k 层（从 1 开始）有 $2^{k-1}$ 个节点。前 k-1 层共有 $2^{k-1} - 1$ 个节点。
对于索引 i 的节点，设它在第 k 层的第 m 个位置（从 0 开始）：
- 下一层的起始索引是 $2^k - 1$
- 它的左子在下一层的第 2m 个位置
- 左子索引 = $2^k - 1 + 2m = 2(2^{k-1} - 1 + m) + 1 = 2i + 1$
数学推导有点繁琐，记住公式即可。
堆的核心性质
结构性质
堆是完全二叉树，因此：
- 有 n 个节点的堆，高度为 $\lfloor \log_2 n \rfloor$
- 从根到任意节点的路径长度不超过 $O(\log n)$
这保证了堆操作的时间复杂度。
堆序性质
- 最大堆：
heap[parent(i)] >= heap[i]对所有 i 成立 - 最小堆：
heap[parent(i)] <= heap[i]对所有 i 成立
推论：
- 最大堆的根（
heap[0]）是最大值 - 最小堆的根（
heap[0]）是最小值
注意：堆不是完全有序的。要获取第二大的值，不能简单地取 heap[1]——第二大的值可能在 heap[1] 或 heap[2]。
最大堆：
90
/ \
85 80 ← 第二大是 85，在左子
/ \
70 75
最大堆：
90
/ \
75 85 ← 第二大是 85，在右子
/ \
70 60堆 vs 其他数据结构
| 操作 | 无序数组 | 有序数组 | 堆 |
|---|---|---|---|
| 获取最值 | O(n) | O(1) | O(1) |
| 插入 | O(1) | O(n) | O(log n) |
| 删除最值 | O(n) | O(1) 或 O(n) | O(log n) |
无序数组插入快，但找最值慢。有序数组找最值快，但插入需要移动元素。堆在两个操作上都有 O(log n) 的平衡性能。
什么时候用堆？
当需要频繁插入且频繁取最值时，堆是最佳选择：
- 优先队列
- 任务调度
- Top K 问题
- 多路归并
如果只需要一次排序，用快排 O(n log n) 更好。如果数据静态且只查询最值，排序后直接取首尾即可。
堆与优先队列
优先队列是一个抽象数据类型：
- 每个元素有优先级
- 出队时总是取出优先级最高（或最低）的元素
优先队列可以用多种方式实现：
| 实现方式 | 入队 | 出队 | 适用场景 |
|---|---|---|---|
| 无序数组 | O(1) | O(n) | 很少出队 |
| 有序数组 | O(n) | O(1) | 很少入队 |
| 堆 | O(log n) | O(log n) | 通用场景 |
堆是优先队列最常用的实现。在很多语言中，「优先队列」和「堆」几乎可以互换使用。
JavaScript 中的堆
重要：JavaScript 没有内置堆/优先队列数据结构。
这与 Java（PriorityQueue）、Python（heapq）、C++（priority_queue）不同。在 JavaScript 中，我们需要手动实现堆，或使用第三方库。
最小堆基础框架：
javascript
class MinHeap {
constructor() {
this.heap = [];
}
// 获取父节点索引
parent(i) {
return Math.floor((i - 1) / 2);
}
// 获取左子节点索引
left(i) {
return 2 * i + 1;
}
// 获取右子节点索引
right(i) {
return 2 * i + 2;
}
// 交换两个位置的元素
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// 获取堆大小
size() {
return this.heap.length;
}
// 堆是否为空
isEmpty() {
return this.heap.length === 0;
}
// 获取堆顶元素（最小值），不删除
peek() {
return this.heap[0];
}
// insert 和 extract 在下一章实现
}最大堆只需修改比较逻辑——将"小于"改为"大于"。
自定义比较器：
实际应用中，我们常需要按自定义规则比较。可以在构造函数中传入比较函数：
javascript
class Heap {
constructor(comparator = (a, b) => a - b) {
this.heap = [];
this.comparator = comparator;
}
// comparator(a, b) < 0 表示 a 优先级更高
// 默认 a - b：值小的优先级高（最小堆）
// 传入 (a, b) => b - a：值大的优先级高（最大堆）
}堆的应用场景
1. Top K 问题
找出 n 个数中最大的 k 个。
- 方法一：排序，取前 k 个 → O(n log n)
- 方法二：维护大小为 k 的最小堆 → O(n log k)
用最小堆：遍历数组，始终保持堆中只有 k 个最大的数。新数比堆顶大就替换。
2. 合并 K 个有序链表
使用最小堆，每次取出最小的节点，将其后继加入堆。
3. 数据流的中位数
维护一个最大堆（存较小的一半）和一个最小堆（存较大的一半），保持两个堆大小平衡。
4. 任务调度
按优先级处理任务，优先队列的典型应用。
本章小结
- 堆的定义：完全二叉树 + 堆序性质
- 两种堆：最大堆（父 ≥ 子）、最小堆（父 ≤ 子）
- 数组存储：
parent(i) = (i-1)/2，left(i) = 2i+1，right(i) = 2i+2 - 核心优势：获取最值 O(1)，插入/删除 O(log n)
- 应用场景：优先队列、Top K、多路归并
下一章我们将实现堆的核心操作：插入（上浮）和删除（下沉）。