一文讲明白优先级队列为啥按less排序却是从大到小（转载）

文章出处

牛客网-wayneYM

一文讲明白优先级队列为啥按less排序却是从大到小

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

优先级队列 Priority_queue

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

定义

priority_queue<Type, Container, Functional>

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

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

包含的方法

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

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

利用std比较函数的实例

std自带**_greater_和_less_两个比较方法。他们实现过程使用的是仿函数**和类模板。

仿函数的理解

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() ,就是类似调用函数的，实际上是一个叫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,greater> pq;//升序
//降序队列大顶堆 less 大到小默认
priority_queue <int,vector,less> 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的直观性质)，但是由于出堆的问题，顺序刚好反了过来，所以(less对应的是大顶堆，出堆顺序是从大到小)

n个无序元素构成大顶堆(最后一个节点上浮)
根节点和最后一个元素交换
剩下n-1个元素重新构成大顶堆(根节点下沉)
重复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出数据从小到大升序

方法或容器	less()的顺序(默认)	greater()的顺序	cmp函数 >
priority_queue 全是反过来的	降序大->小	升序小->大	升序小->大
sort	升序小->大	降序大->小
map	升序小->大	降序大->小
map	升序小->大	降序大->小

除了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()的排序顺序

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

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

需要实现的是less(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()实现从小到大排序，则第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;
}
    };