1. C++优先级队列priority_queue的排序规则

1.写在前面：

queue, stack, priority_queue 都是顺序容器适配器，底层使用vector, deque,list实现。

stack所关联的基础容器vector或deque或 list

queue所关联的基础容器是list

prority_queue 所关联的基础容器是vector或deque

priority_queue<type, contain, compare> type是元素类型，contain是顺序容器， compare是排序规则

2.1 优先级队列内的元素是简单类型，如int

默认情况下，优先级队列元素从大到小排列，类似最大堆, 队头是值最大的那个元素

int main ()
{
  int myints[]= {10,60,50,20};
  std::priority_queue<int> first;//构建一个空堆
  std::priority_queue<int> second (myints,myints+4);// 队头元素是60
}

2.2

如何实现队头元素值最小呢？compare参数传入greator

#include <functional> // std::greator
int main ()
{
  int myints[]= {10,60,50,20};
  std::priority_queue<int, std::vector<int>, std::greater<int> >
                            third (myints,myints+4);
}

3.1优先级队列的元素类型是复合类型，如pair

默认情况下，排序规则是先按照pair的first的属性降序排列，如果first相等，则按照second属性降序排序

同理，传入std::greator后，排序规则是先按照pair的first的属性升序排列，如果first相等，则按照second属性升序排列

3.2按照特定排序规则

昨天做题时，遇到这么个问题，首先统计一个字符串的中各个字符的出现次数，存储在map中

接着把map中每个pair加到优先级队列中，排序规则是按照字符出现的次数由大到小排列

// 自定义排序类
class mycomparison
{
bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (pair<char, int>& lhs, pair<char,int>&rhs) const
  {
    if (reverse) return (lhs.second > rhs.second); // 比较结果为true时，lhs的优先级小于rhs的优先级，rhs排在前面，即升序排列
    else return (lhs.second < rhs.second);// 默认情况下，比较结果为true时，lhs的优先级小于rhs的优先级，rhs排在前} 
};


class Solution { public: string reorganizeString(string S) {

　　map<char, int> my_map;
   int length = S.size();
   for(int i = 0; i < length; i++) { my_map[S[i]]++; }//  统计字符个数 
   priority_queue<pair<char, int>,vector<pair<char,int>> ,mycomparison> max_heap; //建立优先级队列，排序规则是按找pair的第二个元素降序排列
   map<char, int>::iterator begin = my_map.begin(); 
   for(begin; begin != my_map.end(); begin++) { max_heap.push(*(begin)); }
　　……
};

这段代码中，对mycomparison类的书写，核心在于重载()函数,如果函数返回值是true，则证明函数中第一个参数的优先级比第二个参数小，优先级小的就该放到后面去

这段代码还有个好处，当我传入mycomparison（true）时，此时就可以实现升序排列，提高了代码的可用行

原文链接: https://www.cnblogs.com/jielearscoding/p/13169034.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/357501

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

1. C++优先级队列priority_queue的排序规则

相关推荐