C++ priority_queue优先队列用法_C++大顶堆与小顶堆的实现

穿越時空 2025-11-25 00:00:00 次阅读

priority_queue是C++中基于堆的容器适配器，默认为大顶堆，可通过greater或自定义比较实现小顶堆及复杂排序。

在C++中，priority_queue 是一个基于堆结构实现的容器适配器，用于自动维护元素的优先级顺序。默认情况下，它是一个大顶堆（最大值始终在队首），但可以通过自定义比较方式变成小顶堆（最小值在队首）。下面详细介绍其基本用法和大小顶堆的实现方法。

1. priority_queue 基本语法与头文件

使用 priority_queue 需要包含头文件： ```cpp #include #include #include ```

基本声明格式为：

std::priority_queue pq;

T：存储的数据类型
Container：底层容器，默认是
Compare：比较函数对象，默认是，生成大顶堆

常见简写形式：

```cpp // 大顶堆（默认） std::priority_queue max_heap;

// 小顶堆（使用 greater） std::priority_queue, std::greater> min_heap;

2. 大顶堆（最大堆）实现
默认的 priority_queue 就是大顶堆，顶部元素为最大值。
```cpp
std::priority_queue max_pq;
max_pq.push(10);
max_pq.push(30);
max_pq.push(20);

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

特点：每次 top() 返回当前最大值，pop() 删除最大值。

3. 小顶堆（最小堆）实现

通过指定 std::greater 作为比较器，可构建小顶堆。 ```cpp 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

注意：必须显式指定容器类型 vector，因为第三个模板参数覆盖默认时，前两个不能省略。

4. 自定义数据类型的优先队列
对于结构体或类，需提供比较逻辑。可通过重载操作符或自定义比较结构体实现。

方法一：重载 zuojiankuohaophpcn 操作符（用于大顶堆）
```cpp
struct Person {
    int age;
    string name;
    bool operator<(const Person& p) const {
        return age < p.age;  // 年龄大的优先级高（大顶堆）
    }
};
std::priority_queue pq;

方法二：自定义比较结构体（更灵活）

struct Compare {
    bool operator()(const Person& a, const Person& b) {
        return a.age > b.age;  // 年龄小的优先级高 → 小顶堆
    }
};
std::priority_queue, Compare> pq;

这种方式适合复杂排序规则，比如先按优先级，再按时间排序等。

基本上就这些。掌握默认大顶堆、小顶堆的写法以及自定义类型处理，就能应对大多数场景了。