04-数据结构/06-priority queue

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

定义

priority_queue<int> pq;                       // 大顶堆（默认）
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆

常用操作

操作	说明
pq.push(x)	插入元素，自动维护顺序
pq.pop()	弹出优先级最高的元素
pq.top()	返回优先级最高的元素
pq.size()	返回元素数量
pq.empty()	判断是否为空

小顶堆的两种写法

方法一：传相反数

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

方法二：使用 greater

priority_queue<int, vector<int>, greater<int>> pq;
pq.push(x);
int val = pq.top();

结构体优先队列

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

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;

自定义比较器

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

应用场景

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