优先队列仿函数

首先优先队列是堆，对于优先队列来说，默认是less进行排序的，也就是大根堆
这里放一段源码，其中priority_queue的结构中priority_queue第一个参数为类型（存放进去的类型），第二个参数为一个容器，源码中container是的类型是vector<_ValT>，第三个参数是比较器，也就是仿函数默认是less<_ValT>

    priority_queue(_Compare, _Container) -> priority_queue;

  template::value_type,
	   typename _Compare = less<_ValT>,
	   typename _Container = vector<_ValT>,

他与sort不同，sort的仿函数可以用类和函数来写，但是优先队列只能用类来实现，C++代码如下：
sort仿函数对类的实现和优先队列仿函数对类的实现都是通过重载（）来实现的

#include 
#include 
#include 
#include 
using namespace std;

// 类的方式实现sort仿函数
class camp{
public:
    bool operator()(int a, int b){
        return a > b;
    }
};

// 函数的形式实现sort仿函数
bool cmp(int a, int b){
    return a > b;
}

// 类的方式实现priority_queue仿函数（按照pair的第二个参数排）
class cp{
public:
    bool operator()(pair a, pair b){
        return a.second > b.second;
    }
};

int main(){
    vector vec = {2,1,3,4,2,5,5,23,13,22};
    // sort(vec.begin(), vec.end());
    // for(auto x : vec){
    //     cout << x << " ";
    // }
    // cout << endl;
    // sort(vec.begin(), vec.end(), cmp);
    sort(vec.begin(), vec.end(), camp());
    for(auto x : vec){
        cout << x << " ";
    }
    cout << endl;

    // 优先队列的仿函数，只能用类来实现，且前面要加vector
    priority_queue, vector>, cp> pq;
    // 给priority_queue赋值的部分，赋值形式是pair
    for(int i = 0; i < 20; ++i){
        pair tmp(i, i+1);
        pq.push(tmp);
    }

    while(!pq.empty()){
        pair tmp = pq.top();
        cout << tmp.first << "_" << tmp.second << " ";
        pq.pop();
    }
    cout << endl;

    return 0;
}

输出

23 22 13 5 5 4 3 2 2 1 
0_1 1_2 2_3 3_4 4_5 5_6 6_7 7_8 8_9 9_10 10_11 11_12 12_13 13_14 14_15 15_16 16_17 17_18 18_19 19_20 

官方源码实现的less，与本文实现基本一致

  template
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

priority_queue的仿函数在实现的时候会发现符号 > 大于号代表小根堆（greater）；符号 < 小于号代表大根堆（less）。主要的原因在于priority_queue是堆而非队列，堆的内部实现是vector（可以转换为树），每次出堆的时候 实际上是堆顶元素和最后一个元素互换。如果继续将数据缓存在vector中（不用出堆，只是实现堆的内部排序），所有元素形成的数组就是升序的。

例如排好的大顶堆[4，3，2，1]
第一次 4 和 1 换，之后调整之前的顺序
[3，2，1，{4}]
第二次是 3 和 1 换，之后调整之前的顺序
[2，1，{3，4}]
第三次是 2 和 1 换，之后调整之前的顺序
[1，{2，3，4}]
之后可以得到全部的顺序
如果将出堆的顺序保留在vector中那么数字的排序变成递增，符合less的 < 的原则，所以less是大顶堆（可以理解成栈一样，出去的顺序是和内部顺序相反的）