写在前面: 如果你一直纠结为啥自定义明明是greater<>但是出堆却是从小到大，看完这篇文章你就懂了！

优先级队列 Priority_queue

这是一个拥有权值queue，其内部元素按照元素的权值排列。权值较高者排在最前优先出队。其中缺省情况下系统是通过一个max-heap以堆实现完成排序特性，表现为一个以vector表现的完全二叉树。

定义

priority_queue<Type, Container, Functional>

其中Type代表数据类型，Container代表容器类型，缺省状态为vector; Function是比较方式，默认采用的是大顶堆(less<>)。

//升序队列  小顶堆 great 小到大
priority_queue <int,vector<int>,greater<int> > pq;
//降序队列  大顶堆 less  大到小 默认
priority_queue <int,vector<int>,less<int> > pq;

包含的方法

• top() 访问队头
• empty()
• size()
• push() / emplace
• pop
• swap

如何自定义比较函数(主要讲仿函数已了解可跳过)

利用std比较函数的实例

std自带greater<int>和less<int>两个比较方法。他们实现过程使用的是仿函数和类模板。

仿函数的理解

greater和less是std实现的两个仿函数。

//
//注意到  return的符号和名字是相同的。
template <class T> struct greater {
  bool operator() (const T& x, const T& y) const {return x>y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

template <class T> struct less {
  bool operator() (const T& x, const T& y) const {return x<y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

operator()的重载

这个可以重载括号运算符，与==，<，>这类运算符相同。

案例:

class test{
    void operator()(int x){
    cout<<x<<endl;
    }
}
int main()
{
    test t;
    t(10);
    return 0;
}
//输出10

仿函数

仿函数就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

• 仿函数是一个类，不是函数
• 仿函数重载了()，使得可以类似调用函数那样调用实例。(所以大小堆的调用是greater<int>() ,就是类似调用函数的，实际上是一个叫greater的模板类，输入的参数类型是int，()是这个模板类的一个函数)

const int CMP_LES = -1;
const int CMP_EQU = 0;
const int CMP_BIG = 1;
class Comparer
{//比较的模板类(还不够泛化)
public:
    Comparer(int cmpType)
    {
        m_cmpType = cmpType;
    }
    bool operator()(int num1, int num2) const
    {
        bool res;
        switch (m_cmpType)
        {
        case CMP_LES:
            res = num1 < num2;
            break;
        case CMP_EQU:
            res = num1 == num2;
            break;
        case CMP_BIG:
            res = num1 > num2;
            break;
        default:
            res = false;
            break;
        }
        return res;
    }
private:
    int m_cmpType;
};

void Swap(int &num1, int &num2)
{//数字交换
    int temp = num1;
    num1 = num2;
    num2 = temp;
}
void SortArray(int array[], int size, const Comparer &cmp)
{//对长度为size的array进行排序  使用cmp这个类方法  cmp就是仿函数的用法
    //冒泡
    for (int i = 0; i < size - 1; ++i)
    {
        int indx = i;
        for (int j = i + 1; j < size; ++j)
        {
            if (cmp(array[indx], array[j]))//仿函数  此处虽然cmp是一个类，但是用法像一个函数
            {
                indx = j;
            }
        }
        if (indx != i)
        {
            Swap(array, array[indx]);
        }
    }
}
void ListArray(int array[], int size)
{
    for (int i = 0; i < size; ++i)
    {
        cout << array << " ";
    }
}

#define ARY_SIZE 10
int main()
{
    int array[ARY_SIZE] = {10, 12, 9, 31, 93, 34, 98, 9, 1, 20};
    cout << "The initial array is : ";
    ListArray(array, ARY_SIZE);
    cout << endl;
    SortArray(array, ARY_SIZE, Comparer(CMP_BIG));
    cout << "The ascending sorted array is :";
    ListArray(array, ARY_SIZE);
    cout << endl;
    SortArray(array, ARY_SIZE, Comparer(CMP_LES));
    cout << "The descending sorted array is : ";
    ListArray(array, ARY_SIZE);
    cout << endl;
    return 0;
}

运行结果：

The initial array is : 10 12 9 31 93 34 98 9 1 20

The ascending sorted array is :1 9 9 10 12 20 31 34 93 98

The descending sorted array is : 98 93 34 31 20 12 10 9 9 1

49行处虽然cmp是一个类，但是用法像一个函数，即仿函数的意义

greater和less的代码实现

greater定义如下

template <class T> struct greater{
    bool operate() (const T& x, const T &y) const{return x>y;}
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
}

less定义如下

template <class T> struct less {
    bool operator() (const T& x, const T& y) const {return x<y;}
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

常见实例

//升序队列  小顶堆 great 小到大
priority_queue <int,vector<int>,greater<int> > pq;//升序
//降序队列  大顶堆 less  大到小 默认
priority_queue <int,vector<int>,less<int> > pq;//降序

实际上是保持优先级最高的元素在[0]的位置，每次pop或者push操作会更新
声明参数
priority_queue<Type, Container, Funcitonal>;
priority_queue<pair<int,int> > pq_pair;//结果先按照pair的first元素降序，first元素相等再按照second元素降序
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >

!!sort和priority_queue为什么顺序不同

可以发现对于sort和priority_queue，使用greater和less类模板是结果不同的。

主要原因是因为priority_queue的内部实现方法是堆，less对应的是大顶堆。在此排序下调用top()得到的是堆顶，也就是取值时是从大到小。push对应的底层函数是push_heap()，每次添加元素入堆时，在默认情况下添加进去的数据作为较小值入堆。

顺序真正不同的根本原因

堆的内部实现是vector，每次出堆的时候 实际上是堆顶元素和最后一个元素互换(把最大元素沉到数组末端)。那么实际上假如没有出堆这一个过程而是继续将数据缓存在vector中，所有元素出堆后，形成的数组就是升序的。只是由于出堆这一过程导致了元素出堆反序了，相当于逆序输出。

一个例子

例如排好的大顶堆[9，5，7，3]。(9是根节点)
第一次出堆的时候9会被移到最后与3交换位置，同时会对3进行下沉保证堆结构，9出堆。
[3，5，7，9]->[7，5，3，|9] (|后的数字代表已经出堆)
第二次出堆 7与3交换位置。( 此时9已经出堆了，只是为了方便后续表达所以保留)
[3，5，|7，9]->[5，3，|7，9]
第三次出堆 5与3交换位置。5出堆
[5，3，|7，9]->[3，|5，7，9]
第四次出堆 3出堆，此时堆为空
[|3，5，7，9]
可以观察到，假如我们将出堆的数保留在vector中的话，数字排序确实是递增的(符合less<t>的直观性质)，但是由于出堆的问题，顺序刚好反了过来，所以(less<t>对应的是大顶堆，出堆顺序是从大到小)</t></t>

1. n个无序元素构成大顶堆(最后一个节点上浮)
2. 根节点和最后一个元素交换
3. 剩下n-1个元素重新构成大顶堆(根节点下沉)
4. 重复2，3直到数组排序完毕

//默认都是less
sort(vec.begin(),vec.end(),less<int>());               //内置类型从小到大   升序
priority_queue <int,vector<int>,less<int> > pql;    //top出数据从大到小   降序

sort(vec.begin(),vec.end(),greater<int>());            //内置类型从大到小     降序 
priority_queue <int,vector<int>,greater<int> > pqg;    //top出数据从小到大   升序

除了priority_queue使用的是堆，导致全部大小比较反了过来，其他均是正常符合逻辑的操作，即判断为func(a,b)判断为true则a在前。只有priority_queue特殊，如果func(a,b)判断为true，优先级队列中b在前。

对比一下的代码

#include <algorithm>
#include <iostream>
#include <queue>
#include<iterator>
using namespace std;
int main(){
    int A[]={1,4,3,7,10};
    const int N=sizeof(A)/sizeof(int);
    vector<int> vec(A,A+N);
    ostream_iterator<int> output(cout," ");    
    cout<<"Vector vec contains:";
    copy(vec.begin(),vec.end(),output);    
    cout<<"\nAfter greater<int>():";
    sort(vec.begin(),vec.end(),greater<int>());//内置类型从大到小 
    copy(vec.begin(),vec.end(),output);
    cout << endl;
    priority_queue <int,vector<int>,greater<int> > pqg;//升序
    for(auto i : vec)     pqg.push(i);
    while(!pqg.empty()){
        cout << pqg.top() << ' ';
        pqg.pop();
    }
    cout << endl;

    cout<<"\nAfter less<int>():";
    sort(vec.begin(),vec.end(),less<int>());   //内置类型小大到大 
    copy(vec.begin(),vec.end(),output);
    cout << endl;
    priority_queue <int,vector<int>,less<int> > pql;//降序 大小
    for(auto i : vec)  pql.push(i);
    while(!pql.empty()){
        cout << pql.top() << ' ';
        pql.pop();
    }
    cout << endl;

    return 0;
}

自定义优先级队列实例

希望排序结果从小到大，(对应great的小顶堆排序方式)

！注意，重写的是仿函数不是函数，cmp应该是一个类或者struct

注意堆排序导致顺序反了过来，如果cmp(a,b) == true在堆中的排序说明b会在a前面，那么要从小到大，应该用>符号。

struct Node{
    int x,y;
    Node(int a = 0 ,int b = 0): x(a),y(b){}
};
struct cmp{
    bool operator() (Node a,Node b){
        if(a.x == b.x)    return a.y>b.y;
        return a.x>b.x;
    }
};
int main(){
    priority_queue<Node, vector<Node>, cmp> pq;
    for(int i = 0; i < 10 ; ++i){
        pq.push(Node(rand(),rand()));
    }
    while(!pq.empty()){
        cout<<pq.top().x<<' '<<pq.top().y<<endl;
        pq.pop();
    }
    return 0;
}

希望从大到小排序，对应less<T>()的排序顺序

并且利用系统自带的仿函数greater或者less。其中greater使用的是>符号，le***的是<符号。了解原理后实际上重载<或>`均可。

希望通过less实现，由于less<T>()的实现借助了<，所以可以通过，重写<符号实现

需要实现的是less<T>(a,b) = true, b会放在前面，此处要实现大的在前，所以要实现less<T>(小数,大数) = true，保留<号原有意义即可

struct Node{
    int x,y;
    Node(int a = 0 ,int b = 0): x(a),y(b){}
};
//需要注意的是priority_queue默认的优先级计算是less<Node>,所以大顶堆应该重写的是operator<
//注意返回应该是> 虽然着很奇怪
bool operator<(Node a ,Node b){
    if(a.x==b.y)    return a.y<b.y;
    return a.x<b.x;
}

int main(){
    priority_queue<Node> pq;//pq队列是从大到小排序的
    return 0; 
}

反之如果希望借助less<T>()实现从小到大排序，则第7 8 行的比较符号应该为>符号。

例题

406. 根据身高重建队列

仿函数cmp类体现了priority_queue的用法和注意事项。

思路全在代码中了，题目本身较容易想出解法，主要在于实现思路。

struct Node{
    int height,overh;
    Node():height(0), overh(0){}
    Node(int _x, int _y): height(_x), overh(_y) {}
};

struct cmp{
    bool operator() (vector<int> x, vector<int> y){
        //前面高的比较少的   拍最前
        //前面高的相同    比较高的排最前
        //先比第二个参数  小到大(就用>号)   然后第一个参数  大到小(小于号<)
        if(x[1]==y[1])    return x[0] < y[0];
        return x[1] > y[1];
    }
};

class Solution {
public:

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //用优先级队列实现O(n2)时间复杂度
        //先按照前面比当前人高 从小到大排
        //当第一个比较数相同，从大到小插入结果数组  因为从小到大插的话  高的人进入排序可能会影响矮的人  前面比他高的人数  需要判断的东西变多了
        priority_queue<vector<int>, vector<vector<int> > ,cmp>  pq;
        for(auto p : people)    pq.push(p);
        vector< vector<int> >  ans;
        int over = 0,pos=0;


        while(!pq.empty()){
            auto cur = pq.top();
            pq.pop();
            over = 0,pos =0;
            //cout<<over<<' '<<cur[0]<<' '<<cur[1]<<endl;
            while( over < cur[1] ){
                //cout<<"jinru"<<endl;
                if( ans[pos][0] >= cur[0] ) over++;
                pos++;
            }
            //在位置
            ans.insert(ans.begin()+pos, cur);
            //cout<<pos<<"插入成功"<<endl;
        }
        return ans;
    }
};

如果你看到了这里，希望这篇文章对你有帮助，能不能给我点个赞呢。
试试水，牛客似乎发blog没人看，发个帖子trytry，也不知道帖子能不能发技术文。