一、堆是什么？先说说我的理解
堆（Heap）这东西，说白了就是一种特殊的完全二叉树。我当年刚学数据结构时，总觉得堆和「堆栈」是一回事，后来被面试官问得哑口无言才搞清楚——堆是一种树形结构，不是内存里的那个堆。
堆有两个核心特征：
- 结构上：它是一棵完全二叉树。什么叫完全二叉树？就是除了最后一层，其他层都是满的，最后一层的节点都靠左排列。
- 值上：每个节点的值，要么大于等于（或小于等于）它的左右孩子节点的值。
根据这个「大于等于」还是「小于等于」，堆分成了两种：
大顶堆（Max Heap）
每个节点的值都 大于等于 它的左右孩子。换句话说，根节点是整个堆里最大的元素。
大顶堆示例：
90
/ \
70 80
/ \ / \
60 50 40 30你看，90 > 70 且 90 > 80，70 > 60 且 70 > 50……每一层都满足这个关系。
小顶堆（Min Heap）
每个节点的值都 小于等于 它的左右孩子。根节点是最小的。
小顶堆示例：
10
/ \
20 30
/ \ / \
40 50 60 70我在项目中遇到过一个问题：用堆来实现定时器任务调度。每次取最近要执行的任务，其实就是从小顶堆里取根节点。嗯，这个场景后面还会细讲。
二、堆的存储结构——数组才是王道
你可能会想：树嘛，用链表存不就行了？
但堆不一样。因为它是完全二叉树，用数组存反而更省空间、更快。我个人的习惯是：只要能用数组，绝不用链表——数组的缓存局部性好，访问快，而且没有指针开销。
数组下标与节点的对应关系
假设数组下标从 0 开始（C语言里就是这样），那么：
- 下标为
i的节点，它的左孩子下标是2*i + 1 - 右孩子下标是
2*i + 2 - 它的父节点下标是
(i - 1) / 2（整数除法）
举个例子，上面那个大顶堆用数组存就是：
int heap[] = {90, 70, 80, 60, 50, 40, 30};
// 下标： 0 1 2 3 4 5 6检查一下：下标 1（值70）的父节点是 (1-1)/2 = 0，也就是 90，没错。左孩子是 2*1+1 = 3，也就是 60，确实 70 > 60，符合大顶堆。
小技巧：如果你习惯下标从1开始，公式会变成：左孩子 2*i，右孩子 2*i+1，父节点 i/2。我个人更推荐从0开始，因为C语言数组天然从0开始，省去一个浪费的空间。
三、堆的核心操作：向下调整与向上调整
堆的插入和删除，本质上就是这两个调整操作。你只要掌握了它们，堆排序、优先队列什么的都不在话下。
1. 向下调整（Heapify Down / Sift Down）
这个操作通常用在 删除根节点 之后。比如我们删掉大顶堆的根节点（最大值），然后把最后一个元素放到根的位置，这时候堆的性质被破坏了，就需要从根开始往下调整。
思路：
- 从当前节点开始，找到它和它的左右孩子中最大的那个
- 如果最大的不是当前节点，就交换，然后继续向下调整
- 直到当前节点比左右孩子都大，或者没有孩子了
void siftDown(int arr[], int n, int i) {
int largest = i; // 先假设当前节点最大
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
// 交换，然后继续向下调整
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
siftDown(arr, n, largest);
}
}我曾经在写堆排序时，因为忘记检查 left < n 这个边界条件，导致数组越界访问。嗯，这种低级错误，犯过一次就再也不会忘了。
2. 向上调整（Sift Up）
这个操作用在 插入新元素 的时候。我们把新元素放到数组末尾，然后一路往上「冒泡」。
思路：
- 从当前节点开始，比较它和父节点
- 如果当前节点比父节点大（大顶堆），就交换
- 继续向上，直到当前节点不比父节点大，或者到达根节点
void siftUp(int arr[], int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (arr[i] <= arr[parent])
break; // 已经满足堆性质
// 交换
int tmp = arr[i];
arr[i] = arr[parent];
arr[parent] = tmp;
i = parent; // 继续向上
}
}注意：向上调整和向下调整的时间复杂度都是 O(log n)，因为堆的高度是 log₂n。但如果你用数组存堆，插入和删除的常数非常小，比链表实现快得多。
四、堆的完整操作流程
我把堆的常用操作整理成了表格，方便你对照：
| 操作 | 方法 | 时间复杂度 | 核心调整 |
|---|---|---|---|
| 插入 | 先放数组末尾，再向上调整 | O(log n) | siftUp |
| 删除根节点 | 用最后一个元素替换根，再向下调整 | O(log n) | siftDown |
| 建堆 | 从最后一个非叶子节点开始，逐个向下调整 | O(n) | siftDown |
| 堆排序 | 建堆 + 反复删除根 | O(n log n) | siftDown |
你可能会问：建堆为什么是 O(n) 而不是 O(n log n)？
原因很简单：大部分节点在底层，调整的深度很小。具体数学推导我就不展开了，你记住结论就行——建堆是线性的，这在面试里经常被问到。
五、知识体系总览
下面这张图是我画的堆知识结构图，帮你理清脉络：
六、避坑指南
最后，分享几个我踩过的坑：
- 数组越界：向下调整时，一定要先检查左右孩子的下标是否在数组范围内。我刚开始写堆排序时，经常因为
left >= n没判断而崩溃。 - 建堆的顺序：建堆要从最后一个非叶子节点开始向下调整，而不是从根开始。从根开始的话，只能保证根节点最大，下面的子树可能还是乱的。
- 大顶堆 vs 小顶堆：比较符号别搞反了。我建议你写代码时，把比较逻辑单独抽成一个函数，比如
bool compare(int a, int b)，这样切换大顶堆和小顶堆只需要改一处。
我的习惯：在写堆相关的代码时，我会先画一个简单的完全二叉树在纸上，然后手动模拟一遍调整过程。代码写完后，再用几个小数据跑一遍，确保每一步都符合预期。这个方法虽然土，但非常有效。
好了，堆的定义、存储结构和两种调整操作就讲到这里。记住一句话：堆就是用数组实现的完全二叉树，核心就两个操作——向上调整和向下调整。把这个搞明白了，后面堆排序、优先队列什么的，都是水到渠成的事。