C++优先队列std::priority_queue使用详解

std::priority_queue是基于堆实现的自动排序容器，默认为最大堆，仅允许访问顶部元素，支持自定义比较器以实现最小堆或结构体排序，常用于Dijkstra算法、任务调度等需动态获取最优先级元素的场景。

std::priority_queue 是 C++ 标准库中定义在 头文件里的容器适配器，用于实现一个自动排序的队列结构。它基于堆（heap）数据结构，默认情况下是一个最大堆，也就是说每次取出的元素都是当前队列中最大的。

优先队列的基本结构特点

std::priority_queue 并不是一个独立的容器，而是基于其他序列容器（如 vector 或 deque）构建的堆结构。其核心特性包括：

• 自动排序：插入元素后，内部会自动调整堆结构，确保优先级最高的元素位于顶部。
• 只能访问顶部元素：只允许访问或移除堆顶元素（即最高优先级），不能遍历或直接访问其他元素。
• 默认是最大堆：使用 std::less 作为比较器，顶部为最大值。
• 底层容器可配置：通常使用 vector 作为默认底层容器，也可以指定 deque 等支持随机访问的容器。

基本用法与常用操作

创建和使用 priority_queue 非常直观。以下是最常见的操作方式：

#include 
#include 

std::priority_queue pq; // 默认最大堆

pq.push(10);
pq.push(30);
pq.push(20);

std::cout << pq.top() << "\n"; // 输出 30
pq.pop();
std::cout << pq.top() << "\n"; // 输出 20

主要成员函数有：

• push(element)：插入元素，并重新调整堆结构。
• pop()：移除堆顶元素（不返回值）。
• top()：返回堆顶元素的引用（最大或最小，取决于比较器）。
• empty()：判断队列是否为空。
• size()：返回元素个数。

自定义比较方式（最小堆或结构体排序）

如果需要最小堆，可以通过指定比较器来实现：

std::priority_queue, std::greater> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(20);
std::cout << min_pq.top() << "\n"; // 输出 10

对于自定义类型，比如结构体，可以重载比较函数或提供仿函数：

struct Person {
    int age;
    std::string name;
};

// 自定义比较器：按年龄升序（小顶堆）
auto cmp = [](const Person& a, const Person& b) {
    return a.age > b.age; // 注意：这里 > 表示优先级更高的是更小的数
};
std::priority_queue, decltype(cmp)> pq_person(cmp);

常见应用场景

std::priority_queue 常用于需要动态维护“最优先”元素的场景：

• 实现 Dijkstra 最短路径算法中的节点选取。
• 合并多个有序链表时，快速获取最小头节点。
• 任务调度系统中，按优先级执行任务。
• 求数据流中第 K 大/小的元素。

基本上就这些。std::priority_queue 使用简单，性能高效，只要理解它是“只能取最大或最小”的自动排序容器，就能避免误用。注意比较器逻辑，尤其是自定义类型时别写反了优先级方向。基本上就这些。