南通网站制作外包,佛山专业网站制作设计,前端性能优化,中国设计师网效果图前言#xff1a;这篇文章我们继续来分享一个c的容器——优先级队列。 一.理解优先级
何为优先级一说#xff1f;实际上就是有顺序的意思。
优先级队列#xff0c;即有顺序的队列#xff0c;是一个无需我们自己进行排序操作#xff0c;在数据传入时就会由容器自己排好序的…前言这篇文章我们继续来分享一个c的容器——优先级队列。 一.理解优先级
何为优先级一说实际上就是有顺序的意思。
优先级队列即有顺序的队列是一个无需我们自己进行排序操作在数据传入时就会由容器自己排好序的队列。
先来看实例 使用该队列同样需要包含头文件#includequeue。
在默认情况下优先级队列是按照从大到小排序的而在数据结构中也有一个能够自主排序没错就是堆。从大到小的顺序也就是大堆。
那么如果想要实现小堆又该怎么办呢只需要增加一下模版参数 至于为什么这样写就是小堆我们再接下来的模拟实现中进行解答。 二.基本框架
堆可以通过父节点或字节点的下标来互相找到对方的下标所以一般情况都以数组为模板。 template class T,class Container vectorTclass priority_queue{public://向上调整void adjust_up(size_t child){int parent (child - 1) / 2;while (child 0){if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;int parent (child - 1) / 2;}else{break;}}}//向下调整void adjust_down(size_t parent){size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child 1] _con[child]){child;}if (_con[child] _con[parent]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}//插入void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}//删除void pop(){swap(_con[_con.size() - 1], _con[0]);_con.pop_back();adjust_down(0);}//队头元素T top(){return _con[0];}//数据个数size_t size(){return _con.size();}//判空bool empty(){return _con.empty();}private:Container _con;};
这里我们直接给出优先级队列的基本常规操作本质就是堆的各种操作不再一一分享。
而我们要重点分享的就是如何切换升降序。 三.仿函数
从名字就能看出这是一个可以冒充函数的家伙先来看例子
template class T
class less
{
public:bool operator()(const T x, const T y){return x y;}
};
这段代码不难理解在一个类中声明了一个运算符重载函数这个函数能够进行大小比较。 再来看这段代码能够发现我们能够直接通过一个对象来进行两个数据之间的比较。
这就是所谓的仿函数。
上述仿函数是进行“小于”比较同样我们也可以在创造一个仿函数来进行“大于”比较。
如此一来我们便可以通过类模板将这两个仿函数用于排序比较。 四.实现可选优先级
直接看代码 //小于比较template class Tclass less{public:bool operator()(const T x, const T y){return x y;}};//大于比较template class Tclass greater{public:bool operator()(const T x, const T y){return x y;}};template class T,class Container vectorT,class compare lessT//注意class priority_queue{//大堆public://向上调整void adjust_up(size_t child){compare com;//注意int parent (child - 1) / 2;while (child 0){if (com(_con[parent], _con[child]))//注意{swap(_con[child], _con[parent]);child parent;int parent (child - 1) / 2;}else{break;}}}//向下调整void adjust_down(size_t parent){compare com;//注意size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child], _con[child 1]))//注意{child;}if (com(_con[parent], _con[child]))//注意{swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}
其中less为小于比较的类而greater为大于比较的类。
而后我们通过使用类模板参数compare将两者整合在一起因为库里的优先级队列默认即为大堆所以我们使用缺省参数默认为less。
前边已经提到使用仿函数就是使用对应类的对象所以我们需要创建compare类的对象com并传入比较内容进行比较。
这里要注意两个比较数据的先后位置要按照到底是谁大于谁而传入正确的先后顺序。 随后就可以按照排序要求对类型进行更改按照我们的代码方式less为降序greater为升序。 总结
优先级队列的分享到这里就结束啦。
目前为止不难看出C的这些容器的底层数据结构都是我们所学习过的所以对于掌握容器的使用并不困难。
喜欢本篇文章记得一键三连我们下期再见~
