C++ priority_queue怎么用_C++优先队列常用操作与自定义排序

priority_queue是C++ STL中基于堆实现的容器适配器，默认为大根堆，支持高效访问最值。包含push、pop、top等操作，适用于Top K问题、Dijkstra算法等场景；通过greater或自定义比较器可实现小根堆及复杂排序逻辑，注意自定义时返回true表示第一个参数优先级更低。

priority_queue 是 C++ STL 中一个非常实用的容器适配器，用于实现堆结构，默认情况下是一个大根堆（最大值优先）。它常用于需要频繁访问最大或最小元素的场景，比如 Dijkstra 算法、合并多个有序链表等。

基本用法与常用操作

priority_queue 定义在 <queue> 头文件中，使用时需包含该头文件。

默认基于 vector 实现，使用 less 比较器，顶部是最大元素。

立即学习“C++免费学习笔记（深入）”；

priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
cout << pq.top(); // 输出 4
pq.pop(); // 移除 4
cout << pq.top(); // 输出 3

通过指定 greater 比较器实现：

priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
min_pq.push(4);
cout << min_pq.top(); // 输出 1

• push(x)：插入元素 x，自动调整堆结构
• pop()：移除堆顶元素（不返回）
• top()：返回堆顶元素（只读）
• empty()：判断是否为空
• size()：返回元素个数

例如：

while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
}

自定义排序规则

当存储的是结构体或类对象时，需要自定义比较方式。

方法一：重载运算符 <

Midjourney

当前最火的AI绘图生成工具，可以根据文本提示生成华丽的视觉图片。

454

查看详情

适用于 struct 或 class，重载小于号以控制优先级。注意：priority_queue 默认是大根堆，所以 较小的元素优先级低。

若想让 a 的优先级高于 b，应使 a < b 为 false。

struct Person {
    string name;
    int age;
    bool operator<(const Person& p) const {
        return age < p.age; // 年龄大的优先（大根堆）
    }
};

priority_queue<Person> pq;
pq.push({"Alice", 25});
pq.push({"Bob", 30});
cout << pq.top().name; // 输出 Bob

更灵活的方式，尤其适合小根堆或多条件排序。

struct Compare {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age; // 默认大根堆逻辑
    }
};
priority_queue<Person, vector<Person>, Compare> pq;

如果想要年龄小的优先（小根堆），改为：

return a.age > b.age;

不能直接用于 priority_queue 模板参数，但可以配合 decltype 使用：

auto cmp = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
pq.push(3); pq.push(1);
cout << pq.top(); // 输出 1

常见应用场景

• Top K 问题：维护大小为 K 的小根堆，遍历数组找出最大的 K 个数
• 合并 K 个有序链表：将每个链表头节点放入最小堆，每次取出最小节点并加入其后继
• 任务调度：按优先级处理任务，高优先级任务先执行

基本上就这些。掌握默认用法、会写自定义比较器，就能应对大多数情况。注意堆不支持遍历和随机访问，只能操作堆顶。自定义排序时，牢记“返回 true 表示第一个参数优先级更低”。

以上就是C++ priority_queue怎么用_C++优先队列常用操作与自定义排序的详细内容，更多请关注php中文网其它相关文章！