api网站网址大全,网站seo分析报告,wordpress主题如何修改语言,icp许可证个人网站#x1f440;樊梓慕#xff1a;个人主页 #x1f3a5;个人专栏#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
#x1f31d;每一个不曾起舞的日子#xff0c;都是对生命的辜负 前言
本篇文章旨在记录博主在模…
樊梓慕个人主页 个人专栏《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
每一个不曾起舞的日子都是对生命的辜负 前言
本篇文章旨在记录博主在模拟实现priority_queue适配器中遇到的一些问题希望与大家共勉。 欢迎大家收藏以便未来做题时可以快速找到思路巧妙的方法可以事半功倍。 GITEE相关代码fanfei_c的仓库 1.priority_queue的介绍
priority_queue顾名思义『 优先级队列』人话堆。
priority_queue就是基于vector容器的堆所以未来涉及到『 堆的应用』都可以使用priority_queue适配器。
默认为大堆。 同样通过模板参数的方式来决定底层容器和构建小堆。
比如 使用『 vector』作为底层容器内部构造『 大堆』结构。 priority_queueint, vectorint, lessint q1; 使用『 vector』作为底层容器内部构造『 小堆』结构。 priority_queueint, vectorint, greaterint q2; 不指定底层容器和内部需要构造的堆结构采用默认即vector、大堆。 priority_queueint q; 比较奇怪的是
构建大堆要传less构建小堆要传greater容易记混。
『 大堆』less就是逐渐变小『 小堆』greater就是逐渐变大。 2.堆的回顾
2.1向上调整算法
向上调整算法的前提是『 祖先是堆』。
以小堆为例
1.给定向上调整的起点孩子节点下标根据起点下标计算双亲节点下标。 孩子节点与双亲结点间的下标关系 childparent*21 || childparent*22;parent(child-1)/2; 2.比较孩子节点与双亲节点数值大小若孩子节点小于于双亲节点则交换两者并将孩子节点的下标更新为之前的双亲节点下标根据最新的孩子节点下标重新计算双亲节点下标重复这一过程直到孩子节点为根节点。 //堆的向上调整小堆
void AdjustUp(vectorint v, int child)
{int parent (child - 1) / 2; //通过child计算parent的下标while (child 0)//调整到根结点的位置截止{if (v[child] v[parent])//孩子结点的值小于父结点的值{//将父结点与孩子结点交换swap(v[child], v[parent]);//继续向上进行调整child parent;parent (child - 1) / 2;}else{break;}}
} 2.2向下调整算法
向下调整算法的前提是『 左右子树是堆』。
以小堆为例
1.给定向下调整的起点双亲节点下标和节点总数根据起点下标计算孩子节点下标。 注意向下调整时若有两个孩子节点则需要确保调整的是较小的孩子节点。 2.比较孩子节点与双亲节点数值大小若孩子节点小于双亲节点则交换两者并将双亲节点的下标更新为之前的孩子节点下标根据最新的双亲节点下标重新计算孩子节点下标重复这一过程直到孩子节点超出节点总数。 //堆的向下调整小堆
void AdjustDown(vectorint v, int n, int parent)
{//child记录左右孩子中值较大的孩子的下标int child 2 * parent 1;//先默认其左孩子的值较小while (child n){if (child 1 n v[child1] v[child])//右孩子存在并且右孩子比左孩子还小{child child 1;//较小的孩子改为右孩子}if (v[child] v[parent])//左右孩子中较小孩子的值比父结点还小{//将父结点与较小的子结点交换swap(v[child], v[parent]);//继续向下进行调整parent child;child 2 * parent 1;}else{break;}}
} 3.构建大小堆的模板参数问题『仿函数 』
这里同样涉及到模板参数的传递问题。
在学习堆时我们知道可以通过改变比较方式从而实现建大堆或者建小堆 但我们不能每次都手动的去改变这个符号从而满足用户需求。
所以这里我们同样可以利用『 仿函数』来解决这一问题。
仿函数是一个类或结构体它重载了operator()运算符使其可以像函数一样被调用。
仿函数的实例可以像函数指针一样传递给STL算法或容器的操作从而实现自定义行为。
如同我们今天的例子_com是less类的实例对象less类重载了操作符()使其类似于函数调用内部实现比较大小的功能返回布尔值_com()就是仿函数该仿函数模拟了函数行为使if的判断条件为真或假从而达到我们、的目的。 函数参数传参是在『 使用时传参』传递的是『 对象』模板参数传参是在『 编译时传参』传递的是『 类型』。 4.模拟实现源码
#pragma oncenamespace F
{//比较方式减小堆templateclass Tclass less{public:bool operator()(const T x, const T y){return x y;}};//比较方式建大堆templateclass Tclass greater{public:bool operator()(const T x, const T y){return x y;}};templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue{public://向上调整void adjust_up(int child){int parent (child - 1) / 2;while (child 0){//通过模板参数Compare确定是否需要交换结点位置if (_com(_con[child],_con[parent])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}//向下调整void adjust_down(int parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _com(_con[child1],_con[child])){child;}if (_com(_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[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;//底层容器Compare _com;//比较方式};
} 如果你对该系列文章有兴趣的话欢迎持续关注博主动态博主会持续输出优质内容
博主很需要大家的支持你的支持是我创作的不竭动力
~ 点赞收藏关注 ~
