什么是二叉堆
二叉堆（Binary Heap）是一种基于完全二叉树的数据结构，常用来实现优先队列。它分两类：
- 最大堆：任意父节点的键值 ≥ 子节点，堆顶是最大值；
- 最小堆：任意父节点的键值 ≤ 子节点，堆顶是最小值。
“完全二叉树”意味着除最后一层外其他层都满，且最后一层节点靠左对齐——这个性质让堆可以非常紧凑地存储在数组里。
数组存储与下标计算
由于是完全二叉树，堆可以用数组直接存储，不需要指针。根据根节点下标不同有两种约定：
- 根节点下标为 1：左子
2n，右子2n+1，父节点n/2（首元素留空占位）； - 根节点下标为 0：左子
2n+1，右子2n+2，父节点(n-1)/2。
例如根下标为 1 的堆数组 [_, 1, 2, 3, 4, 5, 6, 7]，节点 3 的两个子节点是 6 和 7。下标 0 的约定更常见于竞赛和工程实现，下文代码采用它。
核心操作
1. 插入（上浮）
把新元素追加到数组末尾，然后不断与父节点比较，若违反堆性质就交换，直到满足堆性质或到达根。时间复杂度 O(log n)。
2. 删除堆顶（下沉）
用末尾元素覆盖堆顶，删除末尾，然后从根开始与（最小堆中）较小的子节点交换，逐层下沉直到恢复堆性质。时间复杂度 O(log n)。
3. 建堆
- 自顶向下：逐个调用插入，总代价 O(n log n)；
- 自底向上（Floyd 算法）：从最后一个非叶子节点开始依次下沉，总代价 O(n)——因为越靠近叶子的节点需要下沉的次数越少。
代码实现（C++ 最小堆）
#include <bits/stdc++.h>
using namespace std;
class PriorityQueue {
private:
vector<int> a; // 下标从 0 开始的最小堆
// 上浮：新插入的元素向上调整
void up(int i) {
while (i > 0) {
int p = (i - 1) / 2;
if (a[p] <= a[i]) break;
swap(a[p], a[i]);
i = p;
}
}
// 下沉：堆顶元素向下调整
void down(int i) {
int n = a.size();
while (true) {
int l = 2 * i + 1, r = 2 * i + 2;
int smallest = i;
if (l < n && a[l] < a[smallest]) smallest = l;
if (r < n && a[r] < a[smallest]) smallest = r;
if (smallest == i) break;
swap(a[i], a[smallest]);
i = smallest;
}
}
public:
void push(int v) {
a.push_back(v);
up(a.size() - 1);
}
int top() { return a[0]; }
void pop() {
a[0] = a.back();
a.pop_back();
if (!a.empty()) down(0);
}
bool empty() { return a.empty(); }
};
复杂度与应用场景
| 操作 | 时间复杂度 |
|---|---|
| 查询堆顶 | O(1) |
| 插入 / 删除堆顶 | O(log n) |
| 建堆（Floyd） | O(n) |
| 合并两个堆 | O(n+k)（拼接后重建） |
典型应用：
- 堆排序：反复取出堆顶即可完成排序，O(n log n) 且原地；
- 优先队列：任务调度、Dijkstra 最短路、Huffman 编码；
- Top K 问题：维护大小为 K 的最小堆，扫描一遍即可找出最大的 K 个元素。
易错点提醒
- 下沉时选”较小（最小堆）”的子节点交换，写反就退化成错误的堆；
- 子节点下标计算要区分根下标约定（0 还是 1），混用是最常见的 bug 来源；
pop前记得判空，删除后堆为空时不能再访问top()。