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

穿越時空 2025-12-30 00:00:00 次阅读

priority_queue默认为大顶堆，可通过std::greater或自定义比较器实现小顶堆及结构体排序，关键在于比较函数返回true时表示前者优先级更低。

在C++中，priority_queue 是一个基于堆实现的容器适配器，默认情况下是一个大顶堆（最大值优先）。但在实际编程中，我们经常需要自定义排序规则，比如让最小值优先，或者根据结构体的某个字段排序。本文将详细介绍 priority_queue 的基本用法和如何进行自定义排序。

默认优先队列（大顶堆）

默认情况下，priority_queue 使用 std::less 作为比较函数，因此顶部元素是最大的。

#include 
#include 

int main() {
    std::priority\_queue pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";  // 输出：30 20 10
        pq.pop();
    }
    return 0;
}

小顶堆实现（最小值优先）

要实现小顶堆，只需指定第三个模板参数为 std::greater。

#include 
#include 
#include   // std::greater

std::priority\_queue, std::greater> min_pq;
min_pq.push(10);
min_pq.push(30);
min_pq.push(20);

while (!min_pq.empty()) {
    std::cout << min_pq.top() << " ";  // 输出：10 20 30
    min_pq.pop();
}

注意：必须显式指定容器类型（如 vector），否则编译报错。

自定义结构体排序

如果要对结构体或类对象进行排序，可以通过重载操作符或自定义比较类来实现。

方法一：重载

如果结构体重载了小于号，priority_queue 默认使用 less，会调用 operator

struct Person {
    int age;
    std::string name;
    Person(int a, std::string n) : age(a), name(n) {}
    
    bool operator<(const Person& other) const {
        return age < other.age;  // 年龄大的优先（大顶堆）
    }
};

std::priority\_queue pq;
pq.push(Person(25, "Alice"));
pq.push(Person(30, "Bob"));
// top 是年龄最大的

方法二：自定义比较结构体（推荐）

更灵活的方式是定义一个仿函数（functor）作为比较器。

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

std::priority\_queue, CompareAge> pq;

注意：priority_queue 使用的是“返回 true 表示 a 应该在 b 后面”，所以如果你想让较小的值优先，比较函数应返回 a > b。