如何使用C++的priority_queue 最大堆最小堆实现原理

如何在 c++++ 中使用 priority_queue 实现最大堆和最小堆？1. 默认情况下，priority_queue 是最大堆，如 std::priority_queue max_heap; 可实现每次获取最大值；2. 要实现最小堆，需指定第三个模板参数为 std::greater，如 std::priority_queue, std::greater> min_heap; 以构建最小堆；3. 自定义类型时，应提供比较函数对象，如定义 comparetask 结构体重载 operator() 按 priority 构建最小堆；4. 底层原理基于数组实现的完全二叉树结构，push 和 pop 操作分别触发向上和向下调整；5. 注意 priority_queue 不支持遍历和动态修改元素，适合固定优先级场景。

在 C++ 中，priority_queue 是一个常用的容器适配器，用来实现堆结构。默认情况下，它是一个最大堆（也就是每次取的是当前堆中最大的元素），但通过传入不同的比较函数，也可以轻松实现最小堆。

最大堆的使用方法

默认情况下，priority_queue 就是最大堆。比如：

#include 
std::priority_queue max_heap;

这样声明之后，max_heap.top() 返回的就是当前堆中的最大值。

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

添加元素用 push()，删除顶部元素用 pop()，判断是否为空用 empty()，这些和其它 STL 容器类似。

举个简单的例子：

max_heap.push(3);
max_heap.push(1);
max_heap.push(5);

cout << max_heap.top();  // 输出 5

虽然你插入顺序是 3、1、5，但堆内部自动调整结构，保证最大值始终在顶部。

最小堆怎么实现？

C++ 的 priority_queue 默认不支持最小堆，需要我们手动指定比较函数。通常使用 greater 这个内置的比较器来实现：

#include 
#include 

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

注意模板参数有三个：

HTTPie AI

AI API开发工具

下载

• 第一个是数据类型 int
• 第二个是底层容器，默认是 vector
• 第三个是比较方式，这里用了 greater，也就是“大于”关系，从而构建最小堆

使用起来也是一样：

min_heap.push(4);
min_heap.push(2);
min_heap.push(6);

cout << min_heap.top();  // 输出 2

堆的实现原理简要说明

堆本质上是一种完全二叉树结构，通常用数组实现。最大堆和最小堆的区别在于节点之间的大小关系：

• 最大堆：父节点的值总是大于等于子节点。
• 最小堆：父节点的值总是小于等于子节点。

当调用 push() 时，新元素被放到数组末尾，然后向上调整（heapify up）以保持堆的性质； 当调用 pop() 时，根节点被移除，最后一个元素移到根位置，然后向下调整（heapify down）。

STL 中的 priority_queue 底层就是基于这样的逻辑实现的，只是把比较方式封装成了模板参数。

自定义类型的堆怎么写？

如果你要用自定义类型（比如结构体或类），就需要自己写比较函数或者重载操作符。

比如有一个表示任务优先级的结构体：

struct Task {
    int priority;
    string name;
};

你想按 priority 构建最小堆，可以这样做：

struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;  // 最小堆
    }
};

std::priority_queue, CompareTask> task_queue;

这样就能根据 priority 来排序了。这个技巧在算法题或调度系统中非常实用。

使用注意事项

• priority_queue 不支持直接遍历，只能通过 top() 和 pop() 一个个访问。
• 插入和弹出的时间复杂度都是 O(log n)，效率还不错。
• 如果你需要动态修改堆中的某个元素并重新调整堆，那就不适合用 priority_queue，建议换用 set 或者手写堆结构。

基本上就这些。理解最大堆和最小堆的实现差异，以及如何用模板参数控制比较方式，就可以灵活应对各种场景了。