C++如何使用priority_queue-C++-PHP中文网

c++ stl priority_queue 默认是最大堆，即顶部元素为最大值，因其第三个模板参数默认为 std::less，该比较器使较大元素优先级更高；需显式指定 std::greater 才能实现小顶堆。

c++如何使用priority_queue

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

默认是最大堆，也就是顶部元素是最大值。这是因为 priority_queue 底层用的是 std::less 比较器，它让大元素“优先”上浮。如果你直接写 priority_queue<int></int>，调用 top() 拿到的是当前最大值，不是最小值。

常见误判：看到“queue”就以为先进先出，其实它完全不按插入顺序；看到“priority”就默认是小顶堆，结果调试半天发现数据反了。

要最小堆：写成 priority_queue<int vector>, greater<int>></int></int>
注意第三个模板参数是类型名，不是实例，别漏掉 <int></int>
头文件必须包含 <queue></queue> 和 <functional></functional>（因为 greater 在后者里）

自定义比较函数时为什么不能直接传 lambda

因为 priority_queue 的第三个模板参数必须是类型，而 lambda 类型无法显式写出（每次定义都是匿名唯一类型）。直接传 lambda 会编译报错：template argument for 'Compare' is invalid。

正确做法只有两种：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

用函数对象（struct + operator()），例如：

struct Compare {
    bool operator()(const pair<int>& a, const pair<int>& b) {
        return a.first > b.first; // 小顶堆按 first 排序
    }
};
priority_queue<pair>, vector<pair>>, Compare> pq;</pair></pair></int></int>

用标准函数对象如 greater、less，或 std::greater（C++14 起支持透明比较）

priority_queue 的底层容器能换吗

可以，但仅限于支持随机访问和尾部增删的序列容器，比如 vector 或 deque。默认是 vector，这也是最常用、性能最好的选择。

别碰 list：它不支持 operator[] 和 push_back 的 O(1) 均摊复杂度，编译都过不了。

换 deque 的唯一合理场景是频繁中间插入——但 priority_queue 根本不提供中间操作，所以没必要换
改底层容器不影响接口，但会影响缓存局部性和 reallocation 行为
声明格式固定：priority_queue<t container compare></t>，顺序不能错

往 priority_queue 里 push 指针要注意什么

如果 push 原生指针（比如 new Node），你得自己管内存释放；更危险的是，如果指针指向栈上对象，对象一出作用域，top() 返回的就是野指针。

安全做法只有一条：别 push 原生指针。改用智能指针或值语义。

推荐 priority_queue<shared_ptr>, vector<shared_ptr>>, Compare></shared_ptr></shared_ptr>，自动管理生命周期
如果 Node 很小（比如几个 int），直接存值更高效，避免间接跳转
自定义比较时，对指针比较要格外小心：是比地址？比所指对象？别把 a 写成 <code>*a 却忘了空指针检查

实际用的时候，最常卡住的地方不是语法，而是没想清楚「我到底要最大堆还是最小堆」，以及「我 push 进去的东西，生命周期能不能撑到我 pop 出来那一刻」。这两个问题不确认清楚，后面所有调试都在绕弯。