堆与优先队列：从底层原理到工程实践
堆这个东西，我第一次接触是在大学的数据结构课上。当时觉得不就是个数组嘛，有啥好学的？直到后来做嵌入式项目，需要在资源受限的MCU上做任务调度，才发现堆这个结构真香——它用最少的资源，解决了优先级管理的大问题。
今天咱们就把堆和优先队列彻底讲透。我会从定义讲起，再到存储、操作，最后落到堆排序和优先队列的实现。嗯，内容不少，但都是干货。
一、堆的定义：最大堆与最小堆
堆，本质上是一棵完全二叉树。什么叫完全二叉树？就是除了最后一层，其他层都是满的，最后一层的节点都靠左排列。
堆有两个核心特性：
- 结构特性：完全二叉树
- 堆序特性：任意节点的值 ≥（或 ≤）其子节点的值
根据堆序特性，堆分为两种：
最大堆（大顶堆）：父节点 ≥ 子节点。根节点是最大值。
最小堆（小顶堆）：父节点 ≤ 子节点。根节点是最小值。
我在项目中遇到过一个问题：用最小堆做定时器管理，每次取最近到期的定时器，时间复杂度O(1)，插入和删除都是O(log n)。如果用链表，插入是O(n)，在大规模定时器场景下根本扛不住。
二、堆的存储：用数组实现
堆虽然逻辑上是树，但存储时我们用数组。为什么？因为完全二叉树天然适合数组存储，没有空间浪费。
假设数组下标从0开始，对于下标为 i 的节点：
- 父节点下标：
(i - 1) / 2 - 左子节点下标：
2 * i + 1 - 右子节点下标：
2 * i + 2
举个例子，一个最大堆存储为数组 [50, 30, 40, 10, 20, 35]：
- 根节点50，下标0
- 左子30（下标1），右子40（下标2）
- 30的左子10（下标3），右子20（下标4）
- 40的左子35（下标5）
你看，完全二叉树用数组存，一点空隙都没有。我个人习惯用0基数组，但有些教材用1基，父节点就是 i/2，子节点是 2i 和 2i+1。两种都可以，别搞混就行。
小技巧：用1基数组时，下标0可以存堆的大小，方便管理。我在嵌入式项目中经常这么干，省一个变量。
三、堆的核心操作：插入与删除
堆的操作就两个核心：上浮（swim）和下沉（sink）。理解了这两个，堆就掌握了一半。
3.1 插入操作
插入新元素时，我们把它放到数组末尾（也就是完全二叉树的最后一个位置），然后让它上浮到正确位置。
上浮的过程很简单：
- 比较当前节点和父节点
- 如果违反堆序（最大堆中当前节点更大），交换
- 继续向上比较，直到满足堆序或到达根节点
// 最大堆的上浮操作
void swim(int arr[], int k) {
while (k > 0 && arr[(k - 1) / 2] < arr[k]) {
// 交换当前节点与父节点
int temp = arr[(k - 1) / 2];
arr[(k - 1) / 2] = arr[k];
arr[k] = temp;
k = (k - 1) / 2;
}
}插入的时间复杂度是O(log n)，因为树的高度是log n。
3.2 删除操作（删除堆顶）
删除堆顶元素时，我们先把堆顶和最后一个元素交换，然后删除最后一个元素（原堆顶），再让新的堆顶下沉到正确位置。
下沉的过程：
- 比较当前节点和它的两个子节点
- 如果当前节点不是最大的（最大堆），与较大的子节点交换
- 继续向下比较，直到满足堆序或到达叶子节点
// 最大堆的下沉操作
void sink(int arr[], int n, int k) {
while (2 * k + 1 < n) {
int j = 2 * k + 1; // 左子节点
// 如果右子节点存在且更大，选右子
if (j + 1 < n && arr[j] < arr[j + 1]) {
j++;
}
// 如果当前节点 >= 较大的子节点，结束
if (arr[k] >= arr[j]) {
break;
}
// 交换
int temp = arr[k];
arr[k] = arr[j];
arr[j] = temp;
k = j;
}
}注意：我曾经在删除操作中忘了更新堆大小，导致访问了已删除的元素。这种bug很难查，因为数组里还留着旧数据。一定要维护好当前堆的有效大小。
四、堆排序：O(n log n)的原地排序
堆排序的思路很巧妙：先用数组构建一个最大堆，然后反复把堆顶（最大值）放到末尾，再调整堆。
具体步骤：
- 建堆：从最后一个非叶子节点开始，依次执行下沉操作
- 排序：交换堆顶和最后一个元素，堆大小减1，然后下沉新堆顶
- 重复步骤2，直到堆大小为1
void heapSort(int arr[], int n) {
// 1. 建堆：从最后一个非叶子节点开始下沉
for (int i = n / 2 - 1; i >= 0; i--) {
sink(arr, n, i);
}
// 2. 排序
for (int i = n - 1; i > 0; i--) {
// 交换堆顶和当前末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆
sink(arr, i, 0);
}
}堆排序有几个特点：
- 时间复杂度：O(n log n)，无论最好最坏都是这个
- 空间复杂度：O(1)，原地排序
- 不稳定排序：相等元素的相对顺序可能改变
我记得有一次面试，面试官问我堆排序和快速排序哪个好。我说看场景：如果对最坏情况有要求，堆排序更稳；如果对常数因子敏感，快排更快。他点了点头。
五、优先队列：堆的经典应用
优先队列，说白了就是一个支持插入和取出最大（最小）元素的数据结构。堆是实现优先队列最自然的方式。
用最大堆实现优先队列：
push(x)：插入元素，执行上浮操作pop()：取出堆顶，执行下沉操作top()：返回堆顶元素，O(1)
typedef struct {
int *data;
int size;
int capacity;
} PriorityQueue;
// 初始化
PriorityQueue* createQueue(int cap) {
PriorityQueue *q = malloc(sizeof(PriorityQueue));
q->data = malloc(cap * sizeof(int));
q->size = 0;
q->capacity = cap;
return q;
}
// 插入
void push(PriorityQueue *q, int val) {
if (q->size >= q->capacity) {
// 扩容处理，这里省略
return;
}
q->data[q->size] = val;
swim(q->data, q->size);
q->size++;
}
// 取出堆顶
int pop(PriorityQueue *q) {
if (q->size == 0) return -1;
int maxVal = q->data[0];
q->data[0] = q->data[q->size - 1];
q->size--;
sink(q->data, q->size, 0);
return maxVal;
}工程建议：在实际项目中，优先队列的节点往往不是简单的int，而是一个结构体，包含优先级和数据。这时候比较函数需要自定义。我习惯用函数指针传进去，灵活很多。
六、知识体系总览
下面这张图总结了堆与优先队列的核心知识脉络：
七、避坑指南与经验总结
做了这么多年嵌入式开发，用堆踩过的坑不少，分享几个：
- 数组越界：堆操作中频繁用到
2*i+1和2*i+2，一定要检查下标是否越界。我曾经在边界条件上翻过车，调试了一下午。 - 堆大小维护：插入时size++，删除时size--，这两个操作必须成对出现。少一个，堆就乱了。
- 比较方向：最大堆和最小堆的代码几乎一样，就是比较符号不同。写代码时一定要确认清楚，别把大于号写成小于号。
- 建堆效率：从最后一个非叶子节点开始下沉建堆，时间复杂度是O(n)。如果一个个插入建堆，是O(n log n)。差别很大，记住用前者。
核心总结：堆的本质就是「用数组存储的完全二叉树 + 上浮/下沉操作」。掌握了这两个操作，堆排序、优先队列、Top K问题、中位数问题，全都能迎刃而解。
嗯，堆的内容就讲到这里。代码不多，但思想很重要。你想想看，一个数组，通过下标关系就能模拟出一棵完整的树，还能高效地维护优先级——这种设计，是不是很巧妙？