概念
优先级队列（Priority Queue）是一种特殊的队列，队列中每个元素都附有一个"优先级"。出队时，不再遵循普通队列的 FIFO（先进先出）原则，而是优先级最高（或最低）的元素先出队。
直观类比：医院的急诊室——无论谁先到，病情最重的患者优先就诊。
核心特性
- 插入（insert / enqueue）：将元素连同优先级一起加入队列
- 取最值（peek）：查看优先级最高的元素，不移除
- 取出最值（poll / dequeue）：取出并移除优先级最高的元素
- 不保证全局有序：内部结构只保证堆顶（最值）正确，其余元素顺序不确定
内部实现：二叉堆
绝大多数语言的标准库都用**二叉堆（Binary Heap）**实现优先级队列。
堆的结构
- 用完全二叉树表示，通常以数组存储
- 最小堆（Min-Heap）：父节点 ≤ 子节点，根为最小值
- 最大堆（Max-Heap）：父节点 ≥ 子节点，根为最大值
数组索引关系（从 0 开始）：
| 节点 | 索引 |
|---|---|
| 父节点 | (i-1) / 2 |
| 左子节点 | 2*i + 1 |
| 右子节点 | 2*i + 2 |
核心操作：上浮与下沉
上浮（Sift Up）：插入新元素时，将其放在数组末尾，然后与父节点比较，不满足堆性质则交换，直到满足为止。
下沉（Sift Down）：取出堆顶后，将末尾元素移到堆顶，然后与子节点比较，不满足堆性质则与较小（或较大）的子节点交换，直到满足为止。
时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 插入 | $O(\log n)$ |
| 取出最值 | $O(\log n)$ |
| 查看最值 | $O(1)$ |
| 建堆（heapify） | $O(n)$ |
两种变体
最小优先级队列（Min Priority Queue）
优先级数值最小的元素最先出队。例如：Dijkstra 最短路径算法中，每次选取距离最小的节点。
最大优先级队列（Max Priority Queue）
优先级数值最大的元素最先出队。例如：任务调度中，优先执行优先级最高的任务。
典型应用场景
- 图算法：Dijkstra 最短路、Prim 最小生成树
- Top-K 问题：从海量数据中找出最大/最小的 K 个元素
- 任务调度：操作系统进程调度、定时任务队列
- 事件驱动模拟：按时间戳处理事件
- 中位数维护：用一个最大堆 + 一个最小堆动态维护数据流的中位数
- 合并 K 个有序链表：每次从堆中取出最小节点
与其他数据结构对比
| 结构 | 取最值 | 插入 | 删除任意元素 |
|---|---|---|---|
| 无序数组 | $O(n)$ | $O(1)$ | $O(n)$ |
| 有序数组 | $O(1)$ | $O(n)$ | $O(n)$ |
| 二叉堆 | $O(1)$ | $O(\log n)$ | $O(\log n)$ |
| 平衡 BST | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ |
二叉堆在"频繁插入 + 频繁取最值"的场景下是最佳选择。
注意事项
- 优先级队列不保证同优先级元素的相对顺序（非稳定）
- 标准实现通常不是线程安全的，并发场景需使用专门的并发版本（如 Java 的
PriorityBlockingQueue） - 迭代器遍历不保证按优先级顺序输出，如需有序输出需反复 poll 或对底层数组排序