c++中priority_queue(优先队列)怎么用_c++优先队列使用指南-C++-PHP中文网

c++中priority_queue(优先队列)怎么用_c++优先队列使用指南

冰火之心

发布： 2025-10-09 18:25:01

原创

738人浏览过

优先队列默认为大顶堆，最大元素在顶部，适用于频繁取最值场景。通过greater可实现小顶堆，自定义结构体需重载<或定义比较结构体，常用操作有push、top、pop、empty和size，不支持遍历与迭代器。

c++中priority_queue(优先队列)怎么用_c++优先队列使用指南

优先队列（priority_queue）是 C++ STL 中非常实用的容器适配器，它自动将元素按优先级排序，默认情况下是大顶堆，即最大元素在顶部。不需要手动排序，特别适合处理需要频繁取出最大或最小值的场景，比如 Dijkstra 算法、合并 K 个有序链表等。

基本定义与默认用法

priority_queue 头文件为 <queue>，使用时需包含它。

默认情况下，priority_queue 是基于 vector 实现的大根堆，元素类型通常是 int、double 等基础类型。

#include <queue>
#include <iostream>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);
    
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出：30 20 10
        pq.pop();
    }
    return 0;
}

登录后复制

输出结果是降序，因为最大的数始终在 top。

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

小顶堆的实现方法

如果需要最小值在顶部（小顶堆），可以通过指定比较函数或使用 greater。

常用方式是传入 greater<T> 并显式声明底层容器（如 vector）。

#include <queue>
#include <iostream>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

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

登录后复制

注意模板参数顺序：元素类型、容器类型、比较器。

FashionLabs

AI服装模特、商品图，可商用，低价提升销量神器

查看详情

自定义结构体的优先队列

当元素是结构体或类时，需要定义排序规则。有两种常见方式：

方式一：重载操作符 <

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

priority_queue<Person> pq;
pq.push(Person(25, "Alice"));
pq.push(Person(30, "Bob"));
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;

登录后复制

这种方式更灵活，尤其适合多种排序逻辑的情况。