C++容器适配器——【优先级队列】

前言在之前我们学的数据结构中我们知道顺序表、链表、栈、队列、堆二叉树。但是在C中我们又对这些有了全新的认识本篇博客来详细讲解什么是优先级队列。优先级队列(priority_queue)优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。优先级队列的接口优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。函数声明接口说明priority_queue()/priority_queue(first,last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否则返回falsetop( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素优先级队列不管我是不是有序或者无序插入数据都会按照有序的方式取出数据。#define_CRT_SECURE_NO_WARNINGS1#includeiostream#includevector#includelist#includestack#includequeueusingnamespacestd;#includePriority_queue.hintmain(){px::priority_ququeint,vectorint,Lessintpq;pq.push(5);pq.push(1);pq.push(3);pq.push(8);while(!pq.empty()){coutpq.top() ;pq.pop();}coutendl;std::priority_queueint,vectorint,Greaterintqq;qq.push(2);qq.push(5);qq.push(6);qq.push(1);while(!qq.empty()){coutqq.top() ;qq.pop();}coutendl;return0;}什么是仿函数它的真名叫做函数对象Function Object仿函数 看起来像函数实际上是个对象类的实例平时调用函数是这样add(1,2);仿函数是把一个类对象用 () 调用假装成函数Add add;add(1,2);// 看起来像函数其实是对象在调用 operator()就是一个类里面重载了 operator()structAdd{intoperator()(inta,intb){returnab;}};为什么叫 “仿” 函数因为它不是真函数但用起来和函数一模一样。→ 模仿函数 → 仿函数实现priority_queue思路priority_queue 底层是堆堆需要两个核心操作向上调整 AdjustUp → 插入用向下调整 AdjustDown → 删除堆顶用我要做一个可以切换比较规则的堆Less 就是 小于比较Greater 就是 大于比较它们都重载 operator()传入两个值返回 bool只需通过调用就可以随意建大小堆有仿函数就不用写死所以让仿函数帮我们比较我们就不用运算符比较了。AdjustUp 向上调整插入用新元素插入到最后不断和父亲比较满足比较规则就交换一直往上走到根节点不满足就停止堆已经平衡voidAdjustUp(intchild){compare co;// 创建比较对象intparent(child-1)/2;while(child0)// 没到根节点就继续{if(co(_qe[parent],_qe[child]))// 父与子比较{swap(父,子);// 交换childparent;// 继续往上parent(child-1)/2;}elsebreak;}}AdjustDown 向下调整删除堆顶用删除堆顶先把最后一个元素换到堆顶然后从堆顶往下调整父亲有两个孩子必须先找到更大 / 更小的那个孩子再和父亲比较满足规则就交换继续往下走voidAdjustDown(intparent){size_t childparent*21;// 先找到左孩子compare co;while(child_qe.size()){// 右孩子存在且比左孩子更符合规则if(child1_qe.size()co(_qe[child],_qe[child1]))child;// 父亲和孩子比较if(co(_qe[parent],_qe[child])){swap(父,子);parentchild;childparent*21;}elsebreak;}}push 思路尾插向上调整voidpush(constTx){_qe.push_back(x);AdjustUp(_qe.size()-1);}pop 思路堆顶和最后一个元素交换删除最后一个元素向下调整voidpop(){swap(_qe[0],_qe.back());_qe.pop_back();AdjustDown(0);}top 思路堆顶就是第一个元素constTtop(){return_qe[0];}总结priority_queue 堆堆必须实现 向上调整 向下调整用 仿函数 控制大小堆不写死比较符底层用 vector 存储对外提供标准接口push /pop/top /empty/size完整代码#pragmaonce#includevector//仿函数templateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};namespacepx{templateclassT,classcomtainervectorT,classcompareLessTclasspriority_quque{comtainer _qe;public:voidAdjustUp(intchild){compare co;intparent(child-1)/2;while(child0){if(co(_qe[parent],_qe[child])){swap(_qe[parent],_qe[child]);childparent;parent(child-1)/2;}else{break;}}}voidAdjustDown(intparent){size_t child(parent*2)1;compare co;while(child_qe.size()){if(child1_qe.size()co(_qe[child],_qe[child1])){child;}if(co(_qe[parent],_qe[child])){swap(_qe[child],_qe[parent]);parentchild;child(parent*2)1;}else{break;}}}voidpush(constTx){_qe.push_back(x);AdjustUp(_qe.size()-1);}voidpop(){swap(_qe[0],_qe[_qe.size()-1]);_qe.pop_back();AdjustDown(0);}constTtop(){return_qe[0];}size_tsize()const{return_qe.size();}boolempty()const{return_qe.empty();}};}