C++ STL优先队列用法详解与自定义排序

C++ STL 中的 priority_queue 可通过模板参数自定义比较器来实现最小堆或结构体排序。默认情况下 priority_queue 是一个最大堆，若要创建最小堆，应使用 std::greater<int> 作为比较函数，例如：std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap；对于结构体类型，可采用方法一重载 < 运算符或更推荐的方法二自定义比较器类，如 struct CompareTask 实现优先级排序逻辑；此外，priority_queue 不允许直接修改已有元素的优先级字段，插入和弹出时间复杂度为 O(log n)，且支持用迭代器区间高效初始化队列。

C++ STL 中的 priority_queue 是一种非常实用的数据结构，特别适合处理需要动态维护最大值或最小值的问题。它的底层实现是堆（heap），默认情况下是一个最大堆，也就是说每次取出的是当前队列中最大的元素。

如果你需要用到优先队列，并希望自定义排序方式，比如按某个结构体的字段排序，或者实现一个最小堆，那这篇文章正好能帮到你。

一、基本用法：构造与默认行为

priority_queue 的使用其实很简单，它在 <queue> 头文件里定义。最简单的声明如下：

#include <queue>
std::priority_queue<int> pq;

这个 pq 就是一个默认的最大堆。插入和取出元素的方式如下：

• 插入：pq.push(x);
• 取出最大值：pq.top();
• 删除最大值：pq.pop();

注意，你不能直接遍历 priority_queue，也不能访问中间的元素，只能操作顶部的那个最大值。

二、如何创建最小堆？

有时候我们想让优先队列按照最小值来弹出，这时候就需要改变默认的比较函数。STL 提供了一个模板参数来传入比较器，默认是 less<T>，也就是最大堆。

要创建一个最小堆，可以这样写：

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

这里的三个模板参数分别是：

1. 元素类型
2. 容器类型（一般用 vector）
3. 比较函数对象（这里用了 greater）

现在 min_heap.top() 返回的就是当前队列中最小的元素。

三、自定义结构体的排序方式

当你想用一个结构体作为优先队列的元素时，就需要自己定义比较逻辑了。比如有一个表示任务的结构体：

struct Task {
    int priority;
    std::string name;
};

你想根据 priority 来决定谁先被取出，这时候有两种方法：

方法一：重载运算符

你可以为结构体重载 < 运算符：

bool operator<(const Task& a, const Task& b) {
    return a.priority < b.priority; // 默认是最大堆
}

这样可以直接声明：

std::priority_queue<Task> tasks;

但这种方式会影响全局，可能和其他代码冲突。

方法二：自定义比较器类

更推荐的做法是传入一个比较器类：

struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority < b.priority; // 最大优先级先出
    }
};

std::priority_queue<Task, std::vector<Task>, CompareTask> tasks;

这种写法更清晰也更安全，不会影响其他地方的比较逻辑。

四、一些容易忽略的小细节

• 不能修改已有元素的优先级：一旦元素进入队列，就不能直接修改它的排序依据字段，否则会破坏堆结构。
• 效率问题：虽然插入和弹出的时间复杂度都是 O(log n)，但如果频繁操作，还是要注意性能。
• 初始化方式：可以用一组数据初始化优先队列，例如：

std::vector<int> data = {5, 3, 8, 1};
std::priority_queue<int> pq(data.begin(), data.end());

这比一个个 push 要高效一些。

基本上就这些。掌握这几个点之后，你就能够灵活地使用 priority_queue 了，不管是基础类型还是结构体都能轻松应对。