首页 > 一文讲明白优先级队列为啥按less排序却是从大到小
头像
wayneYM
编辑于 2021-04-27 11:27
+ 关注

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

写在前面: 如果你一直纠结为啥自定义明明是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出数据从小到大   升序
方法或容器 less<T>()的顺序(默认) greater<T>()的顺序 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<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,也不知道帖子能不能发技术文。

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐