sort 升序还是降序？priority_queue 大根堆还是小根堆?

forxtz

发布于 2020-10-10 16:40:21

1.2K0

发布于 2020-10-10 16:40:21

文章被收录于专栏：源懒由码源懒由码

总会忘记，如果写一个比较函数 left < right, 那么，结果是降序还是升序呢。priority_queue是大根堆还是小根堆呢。

所以就写了个测试。

结果表明，如果是 return left < right; 则排序是升序。priority_queue 是大根堆。

如果是 return left > right; 则排序是降序。priority_queue 是小根堆。

std::sort 底层是用快排+堆排+插入（分情况选择用什么排序）实现，平均复杂度为 Nlog(N);

class testless{
public:
    bool operator ()(const int& a,const int& b)const {
            return a<b;
    }
};

class testgreat{
public:
    bool operator ()(const int& a,const int& b)const {
        return a>b;
    }
};

bool mycomparegreat(const int& a,const int& b){
    return a>b;
}

bool mycompareless(const int& a,const int& b){
    return a<b;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2015-09-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

nlog