std::priority_queue是c++中基于堆的容器适配器，默认实现大顶堆，可通过指定比较函数如std::greater构建小顶堆，支持自定义类型与比较规则，底层利用堆算法维护堆序，插入和弹出时间复杂度均为o(log n)，其行为类似堆排序中的动态维护过程，提供高效的最大（或最小）元素访问，适用于任务调度、dijkstra等需优先处理极值的场景。
std::priority_queue 是 C++ 标准库中一个基于堆（heap）实现的容器适配器，常用于快速获取最大（或最小）元素。它底层通常使用 std::vector 或 std::deque，并通过堆算法维护堆序性质。它和堆排序有密切关系，但用途和行为有所不同。
基本用法：默认是大顶堆
默认情况下，std::priority_queue 是一个大顶堆，即每次 top() 返回当前最大值。
#include <queue>
#include <iostream>
int main() {
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(2);
while (!pq.empty()) {
std::cout << pq.top() << " "; // 输出: 4 3 2 1
pq.pop();
}
}
如何创建小顶堆
通过指定比较函数对象来改变排序规则。例如，使用 std::greater 实现小顶堆。
#include <queue>
#include <vector>
#include <functional> // std::greater
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
min_pq.push(4);
min_pq.push(2);
while (!min_pq.empty()) {
std::cout << min_pq.top() << " "; // 输出: 1 2 3 4
min_pq.pop();
}
自定义类型与比较函数
对于结构体或类，需要提供比较方式。可以通过重载操作符或传入仿函数。
立即学习“C++免费学习笔记（深入）”；
struct Task {
int priority;
std::string name;
};
// 自定义比较：优先级数值越小，优先级越高（用于小顶堆）
struct CompareTask {
bool operator()(const Task& a, const Task& b) {
return a.priority > b.priority; // 注意：这里 > 表示更小的优先级先出
}
};
std::priority_queue<Task, std::vector<Task>, CompareTask> task_queue;
task_queue.push({2, "Low"});
task_queue.push({1, "High"});
task_queue.push({3, "Normal"});
while (!task_queue.empty()) {
std::cout << task_queue.top().name << " ";
task_queue.pop();
}
// 输出: High Low Normal
priority_queue 与堆排序的关系
std::priority_queue 的内部实现依赖于堆结构，插入（push）和弹出（pop）操作的时间复杂度都是 O(log n)，而构建过程类似于堆排序中的建堆阶段。
堆排序的过程可以看作是：
- 将数组调整为堆（建堆）
- 反复取出堆顶并调整剩余元素
这正是 priority_queue 在背后做的事。如果你手动对一个 vector 使用 std::make_heap、std::push_heap 和 std::pop_heap，就相当于实现了 priority_queue 的功能。
#include <algorithm>
#include <vector>
#include <iostream>
std::vector<int> v = {3, 1, 4, 2};
std::make_heap(v.begin(), v.end()); // 建大顶堆
while (!v.empty()) {
std::cout << v.front() << " "; // 输出最大值
std::pop_heap(v.begin(), v.end()); // 将最大移到末尾
v.pop_back(); // 移除末尾
}
// 输出: 4 3 2 1
可以看到，这个过程和 priority_queue 的行为一致。因此可以说，priority_queue 提供了堆排序中“动态维护堆”的抽象接口，适合在运行时不断插入删除的场景。
基本上就这些。std::priority_queue 简化了堆的操作，避免手动调用堆算法，适用于 Dijkstra、Huffman 编码、任务调度等需要优先处理最大/最小元素的场合。
