C++ 优先队列（Priority Queue）使用自定义仿函数实现大顶堆

本文将介绍如何在 C++ 中使用自定义仿函数来定义优先队列的比较规则，并以大顶堆为例，详细解释了自定义仿函数的实现过程以及其在优先队列中的应用。

方法一：重载运算符

#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

方法二：重写仿函数

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

代码示例

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

方法二的解释

方法二使用了自定义的仿函数 tmp2 来定义 priority_queue 的比较规则。在 tmp2 中，重载了 () 运算符，使得在插入元素时按照 tmp1 结构体中 x 的大小进行比较，从而实现大顶堆的效果。

具体来说，tmp2 中的重载函数返回的是 a.x < b.x，这表示如果 a 的 x 小于 b 的 x，则返回 true，否则返回 false。根据 priority_queue 的特性，返回 true 表示 a 应该排在 b 之前，也就是说 a 的优先级更高，因此插入时会按照大顶堆的规则进行排序。

在主函数中，通过 priority_queue<tmp1, vector<tmp1>, tmp2> f 来定义一个使用 tmp2 作为比较规则的 priority_queue。然后分别插入了 c、b、a 三个元素。在输出时，可以看到按照大顶堆的规则，元素依次以降序输出。