33DAI：导入1个版本

2026-05-20T18:12:10Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本	2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:28Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

优先队列每次取出的都是优先级最高（默认最大）的元素。

=== 定义 ===

<syntaxhighlight lang="cpp">
priority_queue<int> pq; // 大顶堆（默认）
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
</syntaxhighlight>

=== 常用操作 ===

{| class="wikitable"
! 操作 !! 说明
|-
| <code>pq.push(x)</code>
| 插入元素，自动维护顺序
|-
| <code>pq.pop()</code>
| 弹出优先级最高的元素
|-
| <code>pq.top()</code>
| 返回优先级最高的元素
|-
| <code>pq.size()</code>
| 返回元素数量
|-
| <code>pq.empty()</code>
| 判断是否为空
|}

=== 小顶堆的两种写法 ===

==== 方法一：传相反数 ====

<syntaxhighlight lang="cpp">
priority_queue<int> pq;
pq.push(-x); // 存相反数
int val = -pq.top(); // 取回时再取反
</syntaxhighlight>

==== 方法二：使用 <code>greater</code> ====

<syntaxhighlight lang="cpp">
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(x);
int val = pq.top();
</syntaxhighlight>

=== 结构体优先队列 ===

当元素是结构体时，需要定义比较规则：

<syntaxhighlight lang="cpp">
struct Student
{
int score;
string name;
};

// 重载 < 运算符（注意：priority_queue 默认用 < 判断，但取的是"最大"的）
// 如果想按分数从小到大取，就定义 a.score > b.score（反过来）
bool operator<(const Student &a, const Student &b)
{
return a.score > b.score; // 分数小的优先级高
}

priority_queue<Student> pq;
</syntaxhighlight>

=== 自定义比较器 ===

<syntaxhighlight lang="cpp">
struct cmp
{
bool operator()(const int &a, const int &b)
{
return a > b; // 变成小顶堆
}
};
priority_queue<int, vector<int>, cmp> pq;
</syntaxhighlight>

=== 应用场景 ===

- Dijkstra 最短路径算法
- 合并果子（哈夫曼编码）
- 数据流中的中位数
- 贪心算法中取最优选择

[[Category:数据结构]]
[[Category:三三文档]]

04-数据结构/06-priority queue - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档