【C++】 初阶篇 STL 优先级队列的模拟实现

一、优先级队列定义priority_queue是 C 标准库中的一个容器适配器底层默认用vector存储数据内部维护一个堆结构确保队首元素始终是优先级最高的默认是最大值。三个模板参数分别是T这个容器适配器里面存的数据类型Container这个容器适配器适配的是什么容器Compare仿函数。为什么默认容器是vector因为堆的底层是数组deque的operator[]效率是vector的一半大约。而建堆和访问*21找子等操作会反复调用operator[]所以vector最合适。二、仿函数仿函数实际上是一个类一个重载了()的类。因为在使用的时候像在使用函数所以称之为仿函数。这里的operator()的()是函数的参数列表的那个括号。比如void func()。我先来写几个看看templateclassTclassBig{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassSmall{public:booloperator()(constTx,constTy){returnxy;}};intmain(){Bigintb;Smallints;coutb(2,1)endl;couts(2,1)endl;return0;}对初次接触的读者来说仿函数的调用方式比如s(1,2)确实显得有些陌生和我们熟悉的、等运算符重载的写法很不一样。你可能暂时会疑惑它的实际价值这很正常 —— 当我们后续用它来定制优先级队列的比较规则时这种设计的灵活性和必要性就会清晰地展现出来。三、模拟实现3.1 框架namespaceljm{templateclassT,classContainervectorT,classComparelessTclasspriority_queue{public:private:Container _con;};}这是整个优先级队列的模板定义有三个模板参数T队列中存储的元素类型。Container底层存储数据的容器默认用vector也可以换成deque等支持随机访问的容器。Compare比较规则的仿函数默认是LessT大顶堆可以换成GreaterT实现小顶堆。3.2 AdjustDown 向下调整算法当一个堆顶元素被pop的时候新的堆顶元素就可能要向下调整voidAdjustDown(intparent){intchildparent*21;//先进去while(child_con.size()){//右孩子大于左孩子并且走这一步必须要有右孩子必须存在不能等于size因为size那个下标已经越界if(child1_con.size()_con[child1]_con[child]){child;}if(_con[child]_con[parent]){swap(_con[child],_con[parent]);parentchild;childparent*21;}else{break;}}}这是维护堆结构的核心函数用来在堆顶元素被移除后把新的堆顶向下调整到正确位置从parent的左孩子child parent*21开始。先在左右孩子中用com比较出优先级更高的那个作为真正要交换的child。然后比较父节点和这个孩子节点如果父节点优先级更低就交换它们并继续向下调整。如果父节点优先级已经更高说明调整完成直接跳出循环。3.3 AdjustUp 向上调整算法voidAdjustUp(intchild){intparent(child-1)/2;//parent等于0根节点才会参与交换while(parent0){if(_con[parent]_con[child]){swap(_con[child],_con[parent]);childparent;parent(child-1)/2;}else{break;}}}这个函数用来在新元素插入堆尾后把它向上调整到正确位置计算当前child节点的父节点parent (child-1)/2。如果父节点优先级更低就交换它们并继续向上调整。如果父节点优先级已经更高说明调整完成跳出循环。3.4 范围构造函数templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last){while(first!last){_con.push_back(*first);first;}//这里-2是因为size-1才是最后一个节点,-1/2就是最后一个节点的父亲,每一个要向上调整,哪一个孩子大了就丢上去for(inti(_con.size()-2)/2;i0;i--){AdjustDown(i);}}这个构造函数可以用一段迭代器区间来初始化队列先把区间里的所有元素都插入到底层容器_con中。然后从最后一个非叶子节点的父亲开始依次调用AdjustDown把整个容器调整成一个合法的堆结构。3.5 各种简单的接口pop弹出堆顶元素voidpop(){swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}弹出堆顶元素的步骤先把堆顶元素_con[0]和堆尾元素交换。然后删除堆尾元素也就是原来的堆顶。最后对新的堆顶元素调用AdjustDown重新维护堆的结构。push插入新元素voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}插入新元素的步骤先把新元素插入到底层容器的尾部。然后对这个新插入的元素调用AdjustUp把它向上调整到正确的位置以维持堆的性质。top获取堆顶元素constTtop(){return_con[0];}直接返回底层容器的第一个元素也就是堆顶元素。因为堆顶始终是优先级最高的元素。empty判断队列是否为空boolempty(){return_con.empty();}直接调用底层容器的empty()方法判断队列是否为空。size获取队列元素个数size_tsize(){return_con.size();}直接返回底层容器的大小也就是队列中元素的个数。四、仿函数的利用我们想象一种场景外卖筛选系统要从升序排序改为降序排序这个系统的底层逻辑是堆排序难道还需要手动修改代码才能修正吗所以这里的问题是如何自由修改这个位置的大小比较关系。这里就要用到我们之前学的仿函数了。我们先按照库里的写出仿函数// 仿函数/函数对象templateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};把之前用大于的地方改成_com(x,y)即可如下就是最终版了#define_CRT_SECURE_NO_WARNINGS1#includeiostream#includevectorusingnamespacestd;namespaceljm{// 仿函数/函数对象templateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};templateclassT,classContainervectorT,classCompareLessTclasspriority_queue{public:// 加无参构造函数必须priority_queue(){}// 向下调整堆核心voidAdjustDown(intparent){Compare com;// 定义仿函数对象intchildparent*21;// 左孩子while(child_con.size()){// 选出更大/更小的孩子用仿函数比较if(child1_con.size()com(_con[child],_con[child1])){child;}// 交换 继续调整if(com(_con[parent],_con[child])){swap(_con[child],_con[parent]);parentchild;childparent*21;}else{break;}}}// 向上调整voidAdjustUp(intchild){Compare com;intparent(child-1)/2;while(child0){// 用仿函数比较if(com(_con[parent],_con[child])){swap(_con[child],_con[parent]);childparent;parent(child-1)/2;}else{break;}}}templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last){while(first!last){_con.push_back(*first);first;}for(inti(_con.size()-2)/2;i0;i--){AdjustDown(i);}}voidpop(){swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}constTtop(){return_con[0];}boolempty(){return_con.empty();}size_tsize(){return_con.size();}private:Container _con;};voidtest1(){priority_queueintpq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);pq.push(4);while(!pq.empty()){coutpq.top() ;pq.pop();}coutendl;}}