文章目录priority_queue的基本用法“顶层堆”“顶层堆”“矢量”排序首选队列“自定义排序”
priority_queue的基本用法
头文件队列
priority_queue type、container、function type类型container :实现首选队列的基本容器(默认)元素之间的比较方法(默认) 例如,3333
在STL中,如果只使用第一个参数,则首选队列vector,因为默认情况下“不添加以下两个参数”将vector作为容器,操作者作为比较方法
deque
假设type类型为int,则:
bool empty () const
返回值为true,指示队列为空。
int size () const
返回首选队列中的元素数。
void pop () )
删除队列的顶部元素,即根节点
int top () )
返回队列的顶部元素,但不删除元素。
是语音推送(intarg )
将元素arg插入队列;
顶级头文件functional包含lessint和greaterint
priority_queueint big_heap; //如何构建另一个大堆priority_queueint,vectorint,lessint big_heap2;默认是一个最大堆
# include iostream # include queue # include vector # includefunctionalusingnamespacestd; void t_Big_heap () vectorintvals={ 11,33,55,22,44 }; priority_queueint,vectorint,lessint big_heap; for(autoe:vals ) big_heap.push(e ) e; //show cout ' big _ heap.size (: ' big _ heap.size ) endl; cout ' big _ heap.empty (: ' big _ heap.empty ) ) endl; while (! big_heap.empty () { cout big_heap.top ) }; big_heap.pop (; --------------------此首选队列必须位于priority_queueint、vectorint、greaterint small_heap;最大元素
voidt_SML_HEAP_V2((/小顶按照[0]先升序,如果相等,按照[1] vectorvectorintvec 2i={ 11,13 }、{ 12,14 }、{ 14 } priority_queueint、vectorvectorint、greater Sml_heap; for(autoe:VEC2I ) Sml_heap.push(e ) e; //show cout ' big _ heap.size (: ' SML _ heap.size ) lt
;< endl; cout << "big_heap.empty() :" << Sml_heap.empty() << endl; while(!Sml_heap.empty()){ cout << Sml_heap.top()[0] << " - " << Sml_heap.top()[1] << endl; Sml_heap.pop(); }}----------------------------------------------------------------big_heap.size() :4big_heap.empty() :011 - 1211 - 1312 - 1415 - 16 vector 排序一维的排序
void sort_vec(){ vector<int> vals = {11, 33, 55, 22, 44};// sort(vals.begin(), vals.end(), less<>()); // 升序(默认)// sort(vals.begin(), vals.end(), greater<>()); // 降序// sort(vals.begin(), vals.end()); // 升序 sort(vals.begin(), vals.end(), [&](int &a, int &b){ return a < b; }); // 升序 for(auto &e: vals) cout << e << " ";};-------------------------------------------------------------11 22 33 44 55二维的排序
void sort_vec(){ vector<vector<int>> vec2i= {{11, 13}, {12, 14}, {11, 12}, {15, 16}};// sort(vec2i.begin(), vec2i.end()); // [0] [1] 均升序 sort(vec2i.begin(), vec2i.end(), [&](auto &a, auto &b){ return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]); }); // [0] [1] 均升序// sort(vec2i.begin(), vec2i.end(), [&](auto &a, auto &b){// return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);// }); // [0]升序 如果相等[1]降序 for(auto &vec: vec2i){ cout << vec[0] << " - " << vec[1] << endl; }};-------------------------------------------------------------11 - 1211 - 1312 - 1415 - 16 优先队列自定义排序vector实现
void t_vec(){ vector<string> strs = {"xhh", "mmcy", "mi", "xhz", "abcdef"}; // 排序;长度降序,长度相同时 字典序升序 sort(strs.begin(), strs.end(), [&](string &s1, string &s2){ return (s1.size() > s2.size()) || (s1.size() == s2.size() && s1 < s2); }); for(auto str: strs){ cout << str.size() << " " << str << endl; }}-------------------------------------------------------------6 abcdef4 mmcy3 xhh3 xhz2 mipriority_queue实现
struct cmp{ bool operator()(const string& s1, const string& s2) const{ // 和vector排序写法相反 // a < b : [vec] 升序 [pri] 大顶堆 return (s1.size() < s2.size()) || (s1.size() == s2.size() && s1 > s2); }};void t_prique(){ vector<string> strs = {"xhh", "mmcy", "mi", "xhz", "abcdef"}; priority_queue<string, vector<string>, cmp> pri_que(strs.begin(), strs.end()); while(!pri_que.empty()){ cout << pri_que.top().size() << " " << pri_que.top() << endl; pri_que.pop(); }}-------------------------------------------------------------6 abcdef4 mmcy3 xhh3 xhz2 mi