👀樊梓慕：个人主页
🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》
🌝每一个不曾起舞的日子，都是对生命的辜负
前言
本篇文章旨在记录博主在模拟实现priority_queue适配器中遇到的一些问题，希望与大家共勉。
欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================文章来源地址https://www.toymoban.com/news/detail-818451.html
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 once
namespace 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;//比较方式
};
}=========================================================================
如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容
🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏＋关注 ~🌟文章来源：https://www.toymoban.com/news/detail-818451.html
=========================================================================
到了这里，关于【C++】priority_queue模拟实现过程中值得注意的点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
