【C++】priority_queue模拟实现过程中值得注意的点

👀樊梓慕：个人主页

🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子，都是对生命的辜负

前言

本篇文章旨在记录博主在模拟实现priority_queue适配器中遇到的一些问题，希望与大家共勉。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码：🌟fanfei_c的仓库🌟

=========================================================================

1.priority_queue的介绍

priority_queue顾名思义：『优先级队列』；
人话：堆。

priority_queue就是基于vector容器的堆，所以未来涉及到『堆的应用』都可以使用priority_queue适配器。

默认为大堆。

同样通过模板参数的方式来决定底层容器和构建小堆。

比如：

使用『 vector』作为底层容器，内部构造『大堆』结构。
priority_queue<int, vector<int>, less<int>> q1;
使用『 vector』作为底层容器，内部构造『小堆』结构。
priority_queue<int, vector<int>, greater<int>> q2;
不指定底层容器和内部需要构造的堆结构，采用默认即vector、大堆。
priority_queue<int> q;

比较奇怪的是：

构建大堆要传less，构建小堆要传greater，容易记混。

『大堆』less就是逐渐变小；
『小堆』greater就是逐渐变大。

2.堆的回顾

2.1向上调整算法

向上调整算法的前提是『祖先是堆』。

以小堆为例：

1.给定向上调整的起点（孩子节点下标），根据起点下标计算双亲节点下标。

孩子节点与双亲结点间的下标关系：

child=parent*2+1 || child=parent*2+2;
parent=(child-1)/2;

2.比较孩子节点与双亲节点数值大小，若孩子节点小于于双亲节点，则交换两者，并将孩子节点的下标更新为之前的双亲节点下标，根据最新的孩子节点下标重新计算双亲节点下标，重复这一过程直到孩子节点为根节点。

//堆的向上调整（小堆）
void AdjustUp(vector<int>& 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(vector<int>& v, int n, int parent)
{//child记录左右孩子中值较大的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较小while (child < n){if (child + 1 < n && v[child+1] < 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
{//比较方式：减小堆template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};//比较方式：建大堆template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = std::vector<T>, class Compare = less<T>>class 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[child+1],_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;//比较方式};
}

=========================================================================

如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容

🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏＋关注 ~🌟

=========================================================================