c++ priority_queue用法_c++优先队列详解

std::priority_queue默认是最大堆，顶部元素为最大值，因第三模板参数默认为std::less；需最小堆时应显式指定std::greater并包含头文件。

priority_queue 默认是最大堆还是最小堆

默认是最大堆，也就是顶部元素是队列中最大的那个。这是因为 std::priority_queue 的第三个模板参数默认是 std::less，它让大元素“优先”上浮。

如果你需要最小堆（比如求前 K 小），必须显式传入 std::greater：

std::priority_queue, std::greater> min_heap;

常见错误：直接写 priority_queue, greater> 却没加 std:: 前缀，编译报错 ‘greater’ was not declared in this scope；记得包含头文件 。

如何自定义比较函数或仿函数

当元素是结构体或需要按特定字段排序时，不能依赖默认比较。有两种主流方式：

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

• 提供仿函数类（重载 operator()），作为第三个模板参数
• 用 lambda？不行 —— C++ 标准规定 lambda 类型无法作为模板非类型参数，所以不能直接写在模板里；但可以用 decltype + 变量捕获绕过（仅限 C++20 起支持，且需注意生命周期）

推荐仿函数写法（兼容性好、清晰）：

struct CompareNode {
    bool operator()(const pair& a, const pair& b) {
        return a.first > b.first; // 小 first 优先 → 最小堆
    }
};
std::priority_queue, vector>, CompareNode> pq;

注意：仿函数的逻辑是“返回 true 表示 a 应该排在 b 后面”，即优先级更低 —— 这和直觉相反，容易写反。

priority_queue 没有迭代器，怎么 debug 查看内容

std::priority_queue 不提供迭代器接口，也不能用下标访问，top() 只能看堆顶，size() 和 empty() 是仅有的“观察”手段。

Civitai

AI艺术分享平台！海量SD资源和开源模型。

下载

调试时想看全部元素，唯一安全方法是不断 pop() 并存到临时容器（但会破坏原队列）：

vector dump;
while (!pq.empty()) {
    dump.push_back(pq.top());
    pq.pop();
}
// dump 现在是从大到小（对默认最大堆）

更稳妥的做法：改用底层容器（如 vector）+ 手动调用 make_heap/push_heap/pop_heap，这样你随时可以打印整个 vector。不过这就脱离了 priority_queue 的封装便利性。

性能与底层容器选择的影响

默认底层容器是 std::vector，这是最优选择：连续内存、缓存友好、push_heap/pop_heap 操作复杂度稳定在 O(log n)。

有人尝试换 std::deque —— 编译能过，但实际性能更差：双端队列的随机访问不如 vector 快，而堆操作频繁访问中间索引（如 i*2+1），导致 cache miss 上升。

不能用 std::list：它不支持随机访问，根本无法实例化 priority_queue（编译失败，报错含 no match for ‘operator+’ 或类似提示）。

真正影响性能的其实是比较操作本身 —— 如果自定义比较函数里做了耗时计算（比如字符串长度比对、网络请求模拟），那 O(log n) 的堆操作会被拖慢成 O(log n × cost_of_compare)。