查看“︁04-数据结构/06-priority queue”︁的源代码


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

=== 定义 ===

<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:三三文档]]