什么是优先队列？

你可能已经知道队列（Queue）是一种“先进先出”（FIFO，First-In, First-Out）的数据结构，就像排队买票一样，先排队的人先得到服务。

优先队列则打破了这个规则。它是一种抽象的数据结构，其核心特点是：

所有元素都有“优先级”，取出的元素总是当前队列中优先级最高的那个。

想象一个场景：

• 在普通队列中（FIFO），先来的小明和小红，小明会先被服务。
• 在优先队列中，如果小红的“优先级”比小明高（比如她是 VIP 或情况更紧急），那么无论他们谁先进入队列，小红都会先被服务。

核心特性

1. 插入（Push）： 元素可以以任意顺序插入队列。
2. 获取（Top）： 随时可以查看或获取队列中优先级最高的元素。
3. 删除（Pop）： 删除的永远是优先级最高的元素。

---

优先级的定义：大根堆 vs. 小根堆

在计算机科学中，"优先级最高" 通常意味着：

1. 最大元素优先（大根堆实现）：

   • 优先级： 数值越大，优先级越高。
   • 实现： 使用大根堆（Max Heap）。
   • 效果： 总是取出队列中最大的元素。

2. 最小元素优先（小根堆实现）：

   • 优先级： 数值越小，优先级越高。
   • 实现： 使用小根堆（Min Heap）。
   • 效果： 总是取出队列中最小的元素。

重点： 优先队列通常内部是以堆（Heap）来实现的，因为堆能保证插入和删除优先级最高的元素都非常高效（时间复杂度为 $O(\log n)$）。

---

C++ STL 中的 priority_queue

在 C++ 的标准模板库（STL）中，priority_queue 就是优先队列的实现。它默认使用的是大根堆（最大元素优先）。

你需要包含头文件 <queue> 来使用它。

1. 默认：大根堆（Max Heap）

默认情况下，priority_queue 会将最大的元素视为优先级最高的。

💻 语法与操作

#include <iostream>
#include <queue>
#include <vector> // 默认使用 std::vector 作为底层容器

// 默认是 priority_queue<int, std::vector<int>, std::less<int>>
// std::less<int> 导致最大的元素浮到顶部
std::priority_queue<int> max_pq; 

max_pq.push(30);  // 插入 30
max_pq.push(10);  // 插入 10
max_pq.push(50);  // 插入 50

std::cout << "堆顶 (优先级最高的): " << max_pq.top() << std::endl; 
// 输出: 50 (因为 50 是最大的)

max_pq.pop(); // 删除 50

std::cout << "新的堆顶: " << max_pq.top() << std::endl;
// 输出: 30

2. 自定义：小根堆（Min Heap）

如果你需要让最小的元素拥有最高的优先级，你必须在声明时明确指定比较器。

💻 语法与操作

要实现小根堆，我们需要使用 std::greater<int> 作为比较器（std::greater 的意思是“大于”，它会让最小的元素排在前面）。

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 需要用到 std::greater

// 语法：priority_queue<类型, 底层容器, 比较器>
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq; 

min_pq.push(30);  // 插入 30
min_pq.push(10);  // 插入 10
min_pq.push(50);  // 插入 50

std::cout << "堆顶 (优先级最高的): " << min_pq.top() << std::endl; 
// 输出: 10 (因为 10 是最小的)

min_pq.pop(); // 删除 10

std::cout << "新的堆顶: " << min_pq.top() << std::endl;
// 输出: 30

---

优先队列的应用

优先队列在算法和实际编程中有着广泛的应用：

1. 任务调度： 在操作系统中，根据任务的紧急程度（优先级）来决定先执行哪个任务。
2. 事件模拟： 在模拟系统中，根据事件发生的时间（时间越早优先级越高，即小根堆）来处理事件。
3. 图算法（核心应用）：
   • Dijkstra 算法： 用来求最短路径。它使用一个小根堆来快速找到下一个距离起点最近且未访问的节点。
   • Prim 算法： 用来求最小生成树。它也使用一个小根堆来快速找到下一个连接树和非树节点的最短边。
4. Top K 问题： 在海量数据中，快速找出最大或最小的 K 个元素。

📝 总结（Priority Queue 的操作和复杂度）

操作	描述	C++ STL 函数	时间复杂度（平均）
插入	元素入队	push()	$O(\log n)$
查看	获取优先级最高的元素	top()	$O(1)$
删除	移除优先级最高的元素	pop()	$O(\log n)$
大小	获取队列中元素的数量	size()	$O(1)$

重点回顾： 优先队列是一种高效的工具，它让你能够以对数时间（非常快）来管理和取出集合中优先级最高的元素，而这一切都得益于其底层强大的堆数据结构。