首页 > 讲清楚优先级队列明明选的是less,为什么输出还是从大到小?
头像
wayneYM
发布于 2021-06-02 14:48
+ 关注

讲清楚优先级队列明明选的是less,为什么输出还是从大到小?

写在前面:

容器适配器是STL中重要的组成部分,栈(stack),队列(queue),优先级队列(priority_queue)是最常见的容器适配器。熟悉priority_queue的伙伴应该都知道,优先级队列的出队顺序实际上是逆优先级的,说人话就是如果判断函数是less(a < b = True 则a优先级高于b)出队顺序是降序,即低优先级的元素反而先出队。虽然熟记这一规律并不影响使用,但是为什么是这样这一问题属实折磨了我很久,网上也很难搜到这一小点的资料,故查阅资料写下此文以解决自己的强迫症。

<CPP primer>这一神书中对于优先级队列有真的有这样一段描述「priority_queue允许我们为队列中的元素建立优先级。新加入的元素会排在所有优先级比他低的已有元素之前。」但是我们实际使用过后会发现,例如对于less这一运算符,数字越小优先级越高,如果我们插入1~>5,那么队列顺序应该是[1,2,3,4,5],这样符合书中的描述。但是根据尾进头出的队列特点,出队顺序也应该是1->5,但是熟悉优先级队列的小伙伴都知道默认的less运算符出队顺序是降序也就是5->1。

下面让我们从priority_queue的定义聊起,出队顺序与常识理解反过来的原因

优先级队列 Priority_queue

这是一个拥有权值queue,其内部元素按照元素的权值排列。可实现O(logN)时间复杂度实现插入删除,O(1)时间复杂度取最高权重值。通过一些骚操作可以实现O(1)时间复杂度取中位数等操作。

权值较高者排在最前优先出队。其中缺省情况下系统是通过一个max-heap以堆实现完成排序特性,表现为一个以vector表现的完全二叉树。

定义

priority_queue<type, container, compare>

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

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

包含的方法

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

比较函数(主要讲仿函数已了解可跳过)

首先让我们了解一下比较函数,即lessgreater是什么。

less<int>看似实现的是一个函数的功能,你甚至可以通过less<int>(a,b)调用他去比较a和b的大小。但实际上less<int>是通过一个类重载()实现类似函数调用的功能的,这被称为仿函数

std的比较函数

std已定义好了自带greater<int>less<int>两个比较方法。他们的实现方式是仿函数和类模板。

仿函数的理解

仿函数主要就是通过对类中operator()进行实现,使得类的实例能够实现类似函数的调用操作,这个类就有了类似函数的行为,就是一个仿函数类了,下面是个简单例子。

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

再增加上模版相关的特点,增强泛化能力我们则可以自行实现一个greaterless的仿函数。

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;
}; 

特点

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

常见的实例

//升序队列  小顶堆 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类模板是结果不同的。

先上代码

#include <algorithm>
#include <iostream>
#include <queue>
#include<iterator>
using namespace std;
int main(){
    vector<int> vec = {1,9,2,3,4,7,6,5,8};
    ostream_iterator<int> output(cout," ");    

    cout<<"Vector vec contains: ";
    copy(vec.begin(),vec.end(),output);    

    cout<<"\nAfter greater<int>(): \n";
    cout<<"sort: ";
    sort(vec.begin(),vec.end(),greater<int>());//内置类型从大到小 
    copy(vec.begin(),vec.end(),output);
    cout << endl;
    cout<<"priority_queue: ";
    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>():\n";
    cout<<"sort: ";
    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);
    cout<<"priority_queue: ";
    while(!pql.empty()){
        cout << pql.top() << ' ';
        pql.pop();
    }
    cout << endl;

    return 0;
}
/*输出
Vector vec contains: 1 9 2 3 4 7 6 5 8
After greater<int>():
sort: 9 8 7 6 5 4 3 2 1
priority_queue: 1 2 3 4 5 6 7 8 9

After less<int>():
sort: 1 2 3 4 5 6 7 8 9
priority_queue: 9 8 7 6 5 4 3 2 1
*/

可以观察到,都是使用std的模板类lessgreater,但是使用sortpriority_queue的排序顺序是相反的。

主要原因是priority_queue的内部实现方法是堆,less对应的是大顶堆。在此排序下调用top()得到的是堆顶,也就是取值时是从大到小。

那么问题来了,为什么less需要对应的是大顶堆。less明明代表更小的数具有更高的优先级,这一优先级体现在哪里。

堆的实现

进一步观察堆的内部实现,可以发现堆内部实现依赖vector,因为堆一定是一个完全二叉树,所以使用下标索引直接进行访问是很方便的,不必存成二叉树的结构,使用vector效率更高。

具有以下的特点:

  • 可以在O(logN)的时间复杂度内向中插入元素;
  • 可以在O(logN)的时间复杂度内向中删除元素;
  • 可以在O(1)的时间复杂度内获取顶元素;

堆元素的删除

{12 10 3.5 6.5 8 2.5 1.5 6}为例,这个vector画成堆的形式为下图

image-20210602141433586

堆的删除实现操作为,将堆顶元素(12)与最后一个堆中最后元素(6)进行交换,然后删去最后一个元素(完成了堆顶元素出堆),再对当前vector中的第一个元素(6)进行下沉操作,恢复堆的结构

image-20210602141805540

image-20210602141833560

less含义的体现

一个删除元素的例子

例如排好的大顶堆[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直到数组排序完毕

那么,如果我们在删除堆的时候,省略真实的删除操作,仅仅将其移动到末尾。可以观察到,当堆内元素为空的时候,原数据为{1.5, 2.5, 3.5, 6, 6.5, 8, 10, 12}这时的顺序与less所描述的,元素越小优先级越高相同。所以这就是less含义(数值越小优先级排序越高)的体现。之所以使用中less代表降序,只是由于出堆这一过程导致了元素出堆反序了,相当于逆序输出。

自定义优先级顺序

逆序输出这一点在自定义优先级顺序中也需要注意。同时自定义比较函数时需要注意。重写的应该是仿函数不是函数,自定义的cmp应该是一个类或者struct。

自定义cmp

注意出堆的原因导致顺序反了过来,如果cmp(a,b) == true在堆中的排序说明b会在a前面,那么要从小到大,应该用>符号。自定义cmp中,期望升序,越小越前,大于号。

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;
}

重写operator<

如果希望利用系统自带的仿函数greater或者less。其中greater对应使用的是>符号,less使用的是<符号。了解原理后实际上重载<>均可。

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

一般来说不推荐改变<号的原有意义,即<仍使用<实现,在选择使用less或者greater方法时想好想要的是升序输出还是降序输出。下面的例子中,期望降序输出,所以使用less,重写<操作。

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 行的比较符号应该为>符号。

表格总结

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

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

最后冲一个例题复习下仿函数的实现把。

求点赞求收藏,小白谢谢各位大佬,祝大家offer多多,薪资多多!

例题

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;
    }
};

全部评论

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

相关热帖

近期热帖

近期精华帖

热门推荐