22、优先队列：优先队列的概念、基于堆的优先队列实现、优先队列的应用（任务调度）
优先队列，这个名字听起来挺唬人。其实说白了，它就是一个特殊的队列。
普通队列是先进先出，谁排前面谁先走。但优先队列不一样——它不看谁来得早，而是看谁的优先级高。优先级高的先出队，优先级低的后出队。嗯，就像医院急诊室，危重病人先抢救，轻伤患者等着。
我在项目中遇到过好几次这样的场景：系统里同时来了几十个任务，有的紧急，有的不紧急。如果按顺序处理，紧急任务可能被堵在后面，整个系统就崩了。这时候，优先队列就是救星。
优先队列的核心操作
一个优先队列，至少得支持这几种操作：
- 插入（Insert）：把一个元素扔进队列，同时带上它的优先级。
- 取出最大/最小（Extract Max/Min）：把优先级最高（或最低）的元素拿出来。
- 查看顶部（Peek）：看一眼当前优先级最高的元素，但不取走。
- 修改优先级（Change Priority）：有时候任务做到一半，优先级变了，得能改。
你想想看，如果用普通数组来实现这些操作，插入是 O(1)，但取出最大元素得遍历整个数组，O(n)。数据量一大，这效率就扛不住了。
基于堆的优先队列实现
我个人习惯用二叉堆来实现优先队列。为什么？因为堆能做到插入和取出都是 O(log n)，而且实现起来也不复杂。
二叉堆其实就是一个完全二叉树，但有两种口味：
- 最大堆：每个节点的值都大于等于它的子节点。根节点就是最大值。
- 最小堆：每个节点的值都小于等于它的子节点。根节点就是最小值。
堆的存储方式很有意思。它不用链表，而是用数组。你想想看，完全二叉树天然适合用数组存——根节点放下标 0，左孩子是 2i+1，右孩子是 2i+2。这样既省内存，访问又快。
核心要点：堆的插入和删除，本质上就是上浮（swim）和下沉（sink）两个操作。搞懂了这两个，堆就搞懂了。
我来给你写一个最大堆的插入操作。代码不长，但逻辑很关键：
// 向最大堆中插入一个元素
void insert(int heap[], int *size, int value) {
// 先把元素放到数组末尾
heap[*size] = value;
int i = *size;
(*size)++;
// 然后让它"上浮"到正确位置
while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
// 如果父节点比当前节点小，就交换
int temp = heap[i];
heap[i] = heap[(i - 1) / 2];
heap[(i - 1) / 2] = temp;
i = (i - 1) / 2;
}
}取出最大元素的操作也类似，只不过是把根节点拿走，然后把最后一个元素放到根的位置，再让它下沉到合适的位置。
// 从最大堆中取出最大值
int extractMax(int heap[], int *size) {
if (*size == 0) return -1; // 空堆
int max = heap[0];
heap[0] = heap[*size - 1];
(*size)--;
// 让新的根节点下沉
int i = 0;
while (1) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < *size && heap[left] > heap[largest])
largest = left;
if (right < *size && heap[right] > heap[largest])
largest = right;
if (largest == i) break; // 已经到位
int temp = heap[i];
heap[i] = heap[largest];
heap[largest] = temp;
i = largest;
}
return max;
}我的经验：写堆的时候，最容易出错的其实是下标计算。左孩子是 2i+1，右孩子是 2i+2，父节点是 (i-1)/2。我曾经因为把父节点写成 i/2，导致程序跑飞了整整一个下午。嗯，从那以后我每次写堆都会先画个图确认下标。
优先队列的应用：任务调度
说到优先队列最经典的应用，那必须是任务调度。我在做嵌入式系统的时候，这个场景几乎天天见。
想象一下，你的系统里同时有多个任务在跑：
- 一个键盘输入任务，优先级高，因为用户按了键得立刻响应。
- 一个网络数据包处理任务，优先级中等。
- 一个日志写入任务，优先级低，晚几秒写也没关系。
如果用优先队列来管理这些任务，调度器每次只需要从队列头部取出优先级最高的任务来执行就行了。插入新任务时，根据它的优先级放到合适的位置。
我曾经在一个实时操作系统中做过类似的事情。系统里跑着十几个任务，每个任务都有自己的优先级。调度器每 10 毫秒触发一次，从优先队列里取出当前优先级最高的任务来执行。效果很好，紧急任务从不被耽误。
注意：优先队列不是万能的。如果所有任务的优先级都一样，那它就退化成普通队列了。另外，如果频繁插入和删除，堆的维护开销也不小。我建议在任务数量超过几十个时再用堆，数量少的话，用数组加线性扫描反而更简单。
下面这张图展示了优先队列在任务调度中的核心逻辑：
这张图展示了一个典型的调度流程：新任务带着优先级进入优先队列，堆结构自动维护顺序。调度器每次从堆顶取出优先级最高的任务去执行。任务执行完后，从队列中移除，堆自动调整。
你想想看，如果没有优先队列，调度器就得遍历所有任务来找最高优先级的那个。任务一多，效率就直线下降。用堆的话，不管队列里有多少任务，取出最高优先级任务的时间都是 O(log n)。
避坑指南：我曾经在实现任务调度时犯过一个错误——把优先级数字搞反了。我以为数字越大优先级越低，结果紧急任务全被排在后面。嗯，从那以后我定了一个规矩：优先级数字的含义必须在代码注释里写清楚，而且整个团队统一标准。
优先队列的应用远不止任务调度。比如：
- Dijkstra 最短路径算法：每次从优先队列中取出距离最短的节点。
- 哈夫曼编码：每次合并频率最小的两个节点。
- 数据流中的中位数：用两个堆来维护。
- 操作系统进程调度：根据优先级决定哪个进程先运行。
我个人觉得，优先队列是那种看起来简单，用起来强大的数据结构。它不像红黑树那么复杂，但能解决很多实际问题。你只要掌握了堆的上浮和下沉，基本上就能手写一个优先队列了。
嗯，最后提醒一句：优先队列不是银弹。如果你的数据量很小（比如几十个元素），用数组加线性扫描反而更简单，代码也更不容易出错。别为了用数据结构而用数据结构，要根据实际场景来选。
公众号:蓝海资料掘金营，微信deep3321