【数据结构】优先队列（1）
优先队列（Priority Queue）是一种特殊的队列，它 不遵循“先进先出”（FIFO） 的原则，而是 按照优先级（Priority） 来出队。优先级高的元素 先出队，优先级低的元素 后出队。
1. 优先队列的特点
| 特性 | 说明 |
|---|---|
| 按优先级出队 | 不是“先进先出”，而是“优先级高先出” |
| 动态调整顺序 | 插入新元素时，队列会自动调整顺序 |
| 常用于高效获取最值 | 适合快速获取 最大值 或 最小值 |
2. 优先队列的实现方式
优先队列通常可以用 堆（Heap） 来实现，因为堆能高效地维护元素的优先级顺序。
| 实现方式 | 时间复杂度（插入） | 时间复杂度（删除） | 适用场景 |
|---|---|---|---|
| 数组（无序） | O(1) | O(n)（遍历找最值） | 简单但低效 |
| 有序数组 | O(n)（插入排序） | O(1) | 适用于静态数据 |
| 二叉堆（Binary Heap） | O(log n) | O(log n) | 最常用 |
| 斐波那契堆（Fibonacci Heap） | O(1)（摊还） | O(log n) | 高级优化 |
最常用的是二叉堆（Binary Heap），因为它实现简单且效率较高。
3. 优先队列的操作
| 操作 | 描述 | 时间复杂度（二叉堆） |
|---|---|---|
insert(e) / push(e) | 插入元素 | O(log n) |
deleteMax() / deleteMin() | 删除最高/最低优先级元素 | O(log n) |
peek() / top() | 查看最高/最低优先级元素 | O(1) |
size() | 返回队列大小 | O(1) |
isEmpty() | 判断是否为空 | O(1) |
4. 优先队列的应用
优先队列在算法和实际开发中有广泛的应用，例如：
任务调度
操作系统按优先级执行任务（如高优先级进程先执行）。
Dijkstra 最短路径算法
用优先队列高效获取当前最短路径节点。
Huffman 编码（数据压缩）
优先合并频率最小的字符。
合并 K 个有序链表
用优先队列快速获取最小节点。
游戏 AI（如 A 寻路）*
优先探索最有希望的路径。
5. 代码示例
#include <queue> #include <iostream> int main() { // 默认是大顶堆（降序） std::priority_queue<int> pq; pq.push(3); // 插入元素 pq.push(1); pq.push(4); pq.push(2); while (!pq.empty()) { std::cout << pq.top() << " "; // 输出：4 3 2 1 pq.pop(); // 删除堆顶元素 } return 0; }6. 大顶堆 vs 小顶堆
| 类型 | 特点 | 适用场景 |
|---|---|---|
| 大顶堆（Max Heap） | 堆顶是最大值 | 获取前 K 大元素 |
| 小顶堆（Min Heap） | 堆顶是最小值 | 获取前 K 小元素 |