C++ priority_queue用法详解_C++优先队列自定义排序方法

priority_queue是C++中基于堆的容器适配器，默认为大顶堆，可通过自定义比较器实现小顶堆或复杂类型排序，常用于Dijkstra、Huffman等算法。

在C++中，priority_queue 是一个基于堆实现的容器适配器，用于维护一组元素，并始终能够快速访问最大（或最小）元素。默认情况下，它是一个大顶堆，即优先级最高的元素（最大值）位于顶部。

1. priority_queue 基本用法

头文件：

基本声明方式：

• priority_queue pq;：存储整数的大顶堆
• priority_queue, greater> pq;：小顶堆

常用操作：

• push(x)：插入元素 x
• top()：获取堆顶元素（不删除）
• pop()：弹出堆顶元素
• empty()：判断是否为空
• size()：返回元素个数

示例代码：

#include 
#include 
using namespace std;

int main() {
    priority_queue pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);

    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出：4 3 2 1
        pq.pop();
    }
    return 0;
}

2. 自定义排序：基础结构体

当需要处理复杂类型（如结构体）时，可以通过重载比较函数来自定义优先级规则。

方法一：重载 operator

由于默认使用 less，会调用 operator，所以让“优先级高的”返回 false。

struct Student {
    string name;
    int age;
    // 按年龄从小到大排，年龄小的优先级高（小顶堆效果）
    bool operator<(const Student& other) const {
        return age > other.age;  // 注意：这里反着写
    }
};

priority_queue pq;

注意：operator 返回 true 表示当前对象小于 other。但在大顶堆中，大的在上面。所以为了让年龄小的优先，必须让 age 小的对象“看起来更大”，因此写成 age > other.age。

3. 使用仿函数（Functor）自定义比较器

更清晰的方式是定义一个比较类，实现 operator()。

struct CompareAge {
    bool operator()(const Student& a, const Student& b) const {
        return a.age > b.age;  // 年龄小的优先
    }
};

// 声明时指定第三个模板参数
priority_queue, CompareAge> pq;

此时，返回 true 表示 a 的优先级低于 b，即 b 应该排在前面。这和 sort 的比较函数逻辑一致：true 表示需要交换。

常见错误：误以为返回 true 是“优先”，实际上在 priority_queue 中，比较器的作用是判断谁该被放在下面。如果 cmp(a,b)==true，说明 a 的优先级比 b 低，b 应该浮到上面。

4. 使用 lambda 表达式？不行！但可以用 decltype 配合函数对象

不能直接在模板参数中使用 lambda，但可以配合 decltype 和构造函数使用：

auto cmp = [](const Student& a, const Student& b) { return a.age > b.age; };
priority_queue, decltype(cmp)> pq(cmp);

注意：这里必须把 cmp 作为参数传入构造函数，否则无法推导行为。

适用场景：比较逻辑复杂且只在局部使用时，这种方式更灵活。

5. 常见应用场景

• Dijkstra 算法：取出距离最小的节点
• Huffman 编码：合并频率最小的两棵树
• 合并多个有序链表：用小顶堆维护每个链表的当前头节点
• 滑动窗口最大值：可用 priority_queue 辅助实现

例如：Dijkstra 中通常这样定义：

priority_queue, vector>, greater>> pq;
// 或者自定义比较器，按距离排序

基本上就这些。关键点是理解默认是大顶堆，自定义比较器时要明确“谁优先谁靠上”，返回 true 表示第一个参数优先级更低。不复杂但容易忽略细节。