二叉堆 (Binary Heap)
一种特殊的完全二叉树，存储在数组中，通过 sink（下沉）和 swim（上浮）操作维护堆性质，是优先级队列和堆排序的底层数据结构。
定义
二叉堆（Binary Heap）是一种完全二叉树，通常使用数组（而非链表）存储。根据堆性质分为两种：
- 最大堆（Max Heap）：每个节点都 ≥ 其子节点，堆顶是最大元素
- 最小堆（Min Heap）：每个节点都 ≤ 其子节点，堆顶是最小元素
二叉堆的核心价值在于：它能够动态维护一组元素中的最值，核心操作时间复杂度为 O(log n)。
核心特性
| 特性 | 说明 |
|---|---|
| 结构性质 | 完全二叉树，数组存储 |
| 堆性质 | 最大堆：父 ≥ 子；最小堆：父 ≤ 子 |
| 存储方式 | 数组（索引 0 或 1 开始，常用 1 方便计算父子关系） |
| 父节点索引 | parent(i) = i / 2（1-based）或 (i-1)/2（0-based） |
| 左子节点索引 | left(i) = i * 2（1-based）或 i*2+1（0-based） |
| 右子节点索引 | right(i) = i * 2 + 1（1-based）或 i*2+2（0-based） |
| 树高度 | log n |
基本原理
数组存储与树节点关系（1-based 索引）
int parent(int root) { return root / 2; }
int left(int root) { return root * 2; }
int right(int root) { return root * 2 + 1; }
核心操作：swim（上浮）和 sink（下沉）
上浮（swim）：当节点比父节点大时（最大堆），需要上浮
private void swim(int k) {
while (k > 1 && less(parent(k), k)) {
exch(parent(k), k);
k = parent(k);
}
}
下沉（sink）：当节点比子节点小时（最大堆），需要下沉
private void sink(int k) {
while (left(k) <= N) {
int older = left(k);
if (right(k) <= N && less(older, right(k)))
older = right(k);
if (less(older, k)) break;
exch(k, older);
k = older;
}
}
时间复杂度/性能
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| insert（插入） | O(log K) | K 为堆中元素总数，最多上浮树的高度 |
| delMax/delMin（删除堆顶） | O(log K) | 最多下沉树的高度 |
| max/min（查看堆顶） | O(1) | 直接返回堆顶元素 |
| heapify（建堆） | O(n) | 从底向上 sink，Floyd 算法 |
| 空间复杂度 | O(n) | 存储 n 个元素的数组 |
经典应用
1. 优先级队列（Priority Queue）
基于二叉堆实现，主要 API：
insert(Key e)- 插入元素（加到堆底，再上浮）delMax() / delMin()- 删除并返回最值（堆顶与堆底交换，再下沉）max() / min()- 查看最值（O(1)）
2. 堆排序（Heap Sort）
基于二叉堆的原地排序算法：
- 将数组 heapify 成最大堆
- 反复将堆顶（最大值）与堆尾交换，然后 sink 新堆顶
- 最终数组变为升序排列
时间复杂度：O(n log n)，空间复杂度：O(1)（原地排序）
与类似概念对比
| 维度 | 二叉堆 | 二叉搜索树（BST） | 平衡 BST（红黑树） |
|---|---|---|---|
| 结构 | 完全二叉树 | 任意二叉树 | 平衡二叉树 |
| 性质 | 父 ≥/≤ 子 | 左 < 根 < 右 | 左 < 根 < 右，且平衡 |
| 最值查询 | O(1) | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) | O(log n) |
| 删除最值 | O(log n) | O(log n) | O(log n) |
| 中序遍历有序 | 否 | 是 | 是 |
| 典型应用 | 优先级队列、堆排序 | 查找表、有序遍历 | 有序映射（TreeMap） |
注意事项
- 不是二叉搜索树：二叉堆不保证中序遍历有序
- 数组实现：用数组而非链表，利用完全二叉树的性质
- 0-based vs 1-based：索引计算方式不同，1-based 更直观但浪费一个位置
- 合并困难：二叉堆不适合合并操作（O(n log n)），如需合并可考虑斐波那契堆
应用场景
- 优先级队列：任务调度、Dijkstra 最短路径算法
- 堆排序：原地 O(n log n) 排序，不需要额外空间
- Top K 问题：维护大小为 K 的最小堆/最大堆
- 中位数维护：用一个最大堆 + 一个最小堆
- 实时获取最值：游戏排行榜、系统监控等
经典算法
- 堆排序（Heap Sort）：基于二叉堆的原地排序
- 优先级队列：Dijkstra、Prim 等贪心算法的底层数据结构
- Top K 问题：找第 K 大/小的元素
- 中位数维护：数据流的中位数（LeetCode 295）