优先队列
概述
优先队列（Priority Queue） 是一种维护带键值元素集合 的数据结构，支持插入元素、返回最大（或最小）键值元素、删除并返回最大（或最小）键值元素、以及修改元素键值等操作。
定义
优先队列
优先队列是一种数据结构，维护一个带键值（key）的元素集合 ，支持以下操作：
操作 说明 将元素 插入集合 返回 中具有最大键值的元素 删除并返回 中具有最大键值的元素 将元素 的键值增加到 （要求 ） 也可以实现最小优先队列，将上述操作中的 MAX 替换为 MIN。
核心性质
基于最大堆的实现
优先队列通常以 二叉堆（最大堆）作为底层实现。
各操作的时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 在堆末尾插入后上浮（HEAP-INCREASE-KEY） | ||
| 直接返回 | ||
| 取出 ，将 移至堆顶，调用 MAX-HEAPIFY | ||
| 增大键值后沿父节点方向上浮 |
应用场景
- Dijkstra 最短路径算法：最小优先队列用于选取当前距离最近的顶点。
- Prim 最小生成树算法：最小优先队列用于选取权值最小的边。
- Huffman 编码：最小优先队列用于合并频率最低的节点。
- 事件驱动模拟：按事件时间排序处理。
章节扩展
第6章：堆排序
优先队列是堆排序章节中堆数据结构的重要应用之一。堆排序本身可以看作是优先队列的反复 EXTRACT-MAX 操作。
第24章：单源最短路径
Dijkstra 算法使用最小优先队列来实现贪心选择。
第23章：最小生成树
Prim 算法使用最小优先队列来选取轻量级边。
第21章：最小生成树
Prim算法使用最小优先队列存储轻边端点，EXTRACT-MIN 选择当前最小 key 的顶点，DECREASE-KEY 更新邻接顶点的 key 值。使用二叉堆时 Prim 总时间 O(E lg V)，使用斐波那契堆可优化至 O(E + V lg V)。
第22章：单源最短路径
Dijkstra算法使用最小优先队列存储待处理顶点，EXTRACT-MIN 选择 d 值最小的顶点，DECREASE-KEY 在松弛成功时更新。二叉堆实现 O((V+E) lg V)，斐波那契堆 O(V lg V + E)。
第23章：所有结点对的最短路径
Johnson算法的内层循环对每个源点运行 Dijkstra，因此也依赖最小优先队列。使用斐波那契堆时 Johnson 总时间为 O(V² lg V + VE)。