优先级队列（Priority Queue）
基于二叉堆实现的数据结构，能够按照元素的优先级顺序（而非插入顺序）取出元素。
定义
优先级队列是一种特殊的队列，每个元素都有优先级，出队时总是优先级最高（或最低）的元素先出队。通常使用二叉堆（小顶堆或大顶堆）作为底层实现，保证插入和删除的时间复杂度为 O(log N)。
核心特性
| 特性 | 说明 |
|---|---|
| 底层结构 | 二叉堆（数组实现的完全二叉树） |
| 插入元素 | O(log N) |
| 删除堆顶 | O(log N) |
| 查看堆顶 | O(1) |
| 常见类型 | 小顶堆（最小元素优先）、大顶堆（最大元素优先） |
基本原理
优先级队列底层使用数组实现，但逻辑上是一棵完全二叉树，依靠 swim（上浮）和 sink（下沉）方法维护堆的性质：
- 插入元素：将元素追加到数组末尾，然后调用
swim方法上浮到合适位置 - 删除堆顶：将堆顶与堆尾交换，删除堆尾（原堆顶），然后对新堆顶调用
sink方法下沉
小顶堆示例（最小值在堆顶）:
1
/ \
3 2
/ \
4 5
插入 0: 追加到末尾 -> swim -> 0 上浮到堆顶
删除堆顶: 1 与 5 交换 -> 删除 5 -> sink(1) -> 堆重新平衡
与类似概念对比
| 维度 | 优先级队列 | 普通队列 | 二叉堆 |
|---|---|---|---|
| 出队顺序 | 按优先级 | 按插入顺序（FIFO） | 无出队操作（是底层结构） |
| 底层实现 | 二叉堆 | 数组或链表 | 数组（逻辑上完全二叉树） |
| 时间复杂度 | O(log N) 出入队 | O(1) 出入队 | O(log N) sink/swim |
| 典型应用 | 任务调度、Dijkstra算法 | 广度优先搜索 | 优先级队列的底层 |
时间复杂度/性能
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| push（插入） | O(log N) | 追加后 swim |
| pop（删除堆顶） | O(log N) | 交换后 sink |
| peek（查看堆顶） | O(1) | 直接访问数组[0]或[1] |
| 构建堆（Heapify） | O(N) | 从最后一个非叶子节点开始 sink |
常见类型/变体
1. 小顶堆（Min Priority Queue）
堆顶是最小元素，出队时总是最小的元素先出。用于需要从小到大排序的场景。
2. 大顶堆（Max Priority Queue）
堆顶是最大元素，出队时总是最大的元素先出。用于需要从大到小排序的场景。
核心组件
swim（上浮）操作
新插入的元素从底部向上比较，如果比父节点优先级高（小顶堆：更小；大顶堆：更大），则交换，直到满足堆性质。
sink（下沉）操作
堆顶元素被替换后，从顶部向下比较，如果比子节点优先级低（小顶堆：更大；大顶堆：更小），则与优先级最高的子节点交换，直到满足堆性质。
注意事项
- 优先级队列的底层是二叉堆，必须理解 sink/swim 操作才能正确使用
- 使用数组实现时，通常索引从1开始更方便（父节点 = k/2，子节点 = 2k, 2k+1）
- 优先级队列可以很方便地实现"前K个最大/最小元素"等经典问题
- Java 中的
PriorityQueue、C++ 中的priority_queue都是基于二叉堆实现
常见实现
| 实现 | 底层结构 | 特点 |
|---|---|---|
| SimpleMinPQ（文中示例） | 数组 + 小顶堆 | 教学用简化实现 |
| Java PriorityQueue | 数组 + 小顶堆 | 默认小顶堆，可传入 Comparator |
| C++ priority_queue | 向量 + 大顶堆 | 默认大顶堆，可指定底层容器和比较器 |
关键技巧
堆排序的简单思路
利用优先级队列实现排序：把所有元素塞进去，再取出来。
void sort(int[] nums) {
SimpleMinPQ pq = new SimpleMinPQ(nums.length);
for (int num : nums) pq.push(num);
for (int i = 0; i < nums.length; i++) nums[i] = pq.pop();
}
缺点：空间复杂度 O(N)，因为需要额外的优先级队列。
真正的堆排序
不使用额外空间，直接在原数组上进行 sink/swim 操作（原地堆排序）。
应用场景
- 任务调度：操作系统中按优先级调度进程
- Dijkstra 算法：用优先级队列动态获取当前距离最近的节点
- Prim 算法：用优先级队列选择权重最小的边
- Top K 问题：维护一个大小为 K 的堆
- 哈夫曼编码：用优先级队列合并频率最小的节点
- 堆排序：优先级队列的简单应用（虽然真正的堆排序不需要额外空间）
- 合并k个有序链表：用最小堆快速获取k个节点中的最小值，时间复杂度O(N log k)（见 LeetCode 23）
经典算法
- Dijkstra算法：优先级队列优化的经典应用
- 最小生成树算法：Prim 算法使用优先级队列
- 堆排序：基于优先级队列思路，但原地完成