【数据结构】优先队列（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>
using namespace std;
int main() {
// 默认是大顶堆（降序）
priority_queue<int> pq;
pq.push(3); // 插入元素
pq.push(1);
pq.push(4);
pq.push(2);
while (!pq.empty()) {
cout << pq.top() << " "; // 输出：4 3 2 1
pq.pop(); // 删除堆顶元素
}
return 0;
}6. 大顶堆 vs 小顶堆
| 类型 | 特点 | 适用场景 |
|---|---|---|
| 大顶堆（Max Heap） | 堆顶是最大值 | 获取前 K 大元素 |
| 小顶堆（Min Heap） | 堆顶是最小值 | 获取前 K 小元素 |
（1）基础类型的小顶堆
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// 小顶堆模板参数说明：
// 1. int：元素类型
// 2. vector<int>：底层存储容器（必须支持随机访问）
// 3. greater<int>：比较器，实现“小值优先”
priority_queue<int, vector<int>, greater<int>> min_heap;
// 插入元素
min_heap.push(10);
min_heap.push(5);
min_heap.push(15);
min_heap.push(3);
min_heap.push(8);
// 遍历输出（仅能通过top()+pop()方式，因无迭代器）
cout << "小顶堆出队顺序（从小到大）：";
while (!min_heap.empty()) {
// 获取队首（最小值）
cout << min_heap.top() << " ";
// 删除队首
min_heap.pop();
}
// 输出结果：3 5 8 10 15
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
