编程C++

在priority_queue中自定义比较函数：自定义 HeapCmp 结构体并重载 () 的方式

字数统计: 1k字   |   阅读时长: 4分
, ,

摘要: 在堆中自定义比较函数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

priority_queue

在 C++ 中，priority_queue<int> pq 默认维护的是最小堆，也就是数值越小的越优先。如果展开写，也就是默认是下面这样：

1
2
priority_queue<int> pq; // 最小堆
priority_queue<int, vector<int>, greater<int>> pq; // 最小堆

如果想要最大堆，可以把 greater<int> 改成 less<int>。

1
priority_queue<int, vector<int>, less<int>> pq; // 最大堆

greater<int> 与 less<int>

这里 greater<int> 和 less<int> 的实例都相当于一个比较函数，greater<int> 的实例作为比较函数返回第一个参数是否大于第二个参数；less<int> 的实例作为比较函数返回第一个参数是否小于第二个参数。例如以下代码中，f 的结果是 false，g 的结果是 true。

1
2
bool f = greater<int>()(3, 8);
bool g = less<int>()(3, 8);

在 sort 和 priority_queue 中，上面两个仿函数的含义一样，只是 sort 默认是 less<int>，即从小到大排序，而 priority_queue 默认是 greater<int>，即最小堆。

priority_queue 中自定义比较规则

如果维护的是自定义对象，可以类似自定义排序比较逻辑的方法，定义 HeapCmp 结构体，在其中重载调用运算符（C++ 就是 ()），然后在定义优先级队列时提供 HeapCmp 的实例。代码大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
struct MyObj
{
    // 对象中的数据成员
};

struct HeapCmp
{
    bool operator()(const MyObj& o1, const MyObj& o2) const
    {
        // 比较逻辑：什么叫 o1 小于 o2
    }
};

此时，定义一个维护 MyObj 对象的优先级队列的写法如下：

1
priority_queue<MyObj, vector<MyObj>, HeapCmp> pq;

如果 HeapCmp 的实例在调用时 o1 小于 o2 时返回 true，就相当于 less<int>，那么 pq 就是一个最大堆。

如果想要最小堆，就在 HeapCmp 的 () 中当 o1 大于 o2 时返回 true，相当于 greater<int>。

比较规则中持有状态的问题

如果 HeapCmp 中持有状态，代码大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct MyObj
{
    // 对象中的数据成员
};

struct HeapCmp
{
    State state;
    HeapCmp(State state):state(state){}
    bool operator()(const MyObj& o1, const MyObj& o2) const
    {
        // 比较逻辑：什么叫 o1 小于 o2
        // 结果与 state 有关
    }
};

此时如果还要通过以下方式实例化一个 priority_queue 就不行了，因为代码中 HeapCmp 不是一个实例化的对象：

1
priority_queue<MyObj, vector<MyObj>, HeapCmp> pq;

要解决 HeapCmp 中持有状态的问题，比较方便的解法有通用多态函数包装器 std::function 以及 lambda 表达式两种方案。参考文章：

写法例子

通过定义 HeapCmp 结构体的方式自定义堆的比较规则，在具体的问题中应该怎么写，参考这个例题：自定义堆或优先级队列的比较规则：基于比较函数或键函数。

如果 HeapCmp 中持有状态，则需要通过 std::function 或 lambda 表达式解决，代码模板参考：【模板集锦】自定义比较函数：既有额外信息又有复杂控制逻辑的情况

应用案例

用到上述通过定义 HeapCmp 结构体的方式自定义堆的比较规则的题目或算法，参考下列文章：

Share