如何使用C++的priority_queue 最大堆最小堆实现原理-C++-PHP中文网

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

P粉602998670

发布： 2025-07-14 08:02:02

原创

884人浏览过

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

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

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

最大堆的使用方法

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

#include <queue>
std::priority_queue<int> 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<int> 这个内置的比较器来实现：

#include <queue>
#include <functional>

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

登录后复制

注意模板参数有三个：

堆友

Alibaba Design打造的设计师全成长周期服务平台，旨在成为设计师的好朋友

306

查看详情

第一个是数据类型 int
第二个是底层容器，默认是 vector<int>
第三个是比较方式，这里用了 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<Task, std::vector<Task>, CompareTask> task_queue;

登录后复制

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