C++ priority_queue怎么用_C++优先队列底层实现与自定义比较器

C++中的priority_queue是基于堆实现的容器适配器，默认为大根堆，提供push、pop、top等操作，时间复杂度为O(log n)，可通过std::greater或自定义比较器实现小根堆或自定义优先级，适用于Dijkstra、任务调度等场景。

C++ 中的 priority_queue 是一个基于堆结构实现的容器适配器，用于快速获取最大（或最小）元素。它默认是一个大根堆，即队头始终是当前优先级最高的元素。本文将介绍它的基本用法、底层实现原理以及如何使用自定义比较器。

基本用法与常见操作

priority_queue 定义在 queue 头文件中，使用方式如下：

#include 
#include 

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

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

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

常用成员函数包括：

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

底层实现原理

priority_queue 底层基于 堆（heap） 实现，通常使用 vector 或 deque 作为存储结构。标准库通过 make_heap、push_heap 和 pop_heap 等算法维护堆性质。

每次 push 操作会将元素插入尾部，然后向上调整（上浮）以保持堆序；pop 则将首尾交换后弹出，并向下调整（下沉）恢复堆结构。这两个操作的时间复杂度均为 O(log n)。

由于 priority_queue 是容器适配器，不能直接遍历，也不提供迭代器。

自定义比较器

默认情况下，priority_queue 使用 std::less 构造大根堆。若要改为小根堆，可指定比较器为 std::greater：

std::priority_queue, std::greater> min_pq;
min_pq.push(10);
min_pq.push(5);
min_pq.push(15);
std::cout << min_pq.top();  // 输出 5

对于自定义类型（如结构体），可以重载比较函数或传入函数对象：

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

// 方式一：重载 operator<
bool operator<(const Person& a, const Person& b) {
    return a.age < b.age;  // 年龄大的优先
}

std::priority_queue pq;
pq.push({25, "Alice"});
pq.push({30, "Bob"});
std::cout << pq.top().name;  // 输出 Bob

也可以使用 lambda 表达式配合函数对象（需用 decltype 并传入构造参数）：

auto cmp = [](const Person& a, const Person& b) {
    return a.age < b.age;  // 小根堆逻辑：年龄小的优先
};
std::priority_queue, decltype(cmp)> pq(cmp);

基本上就这些。掌握 priority_queue 的使用和比较器设计，能有效应对涉及优先级调度、Dijkstra 算法、合并 K 个有序链表等典型问题。理解其堆基础也有助于分析性能和调试行为。