C++priority_queue模拟实现
C++priority_queue模拟实现
- 1.priority_queue基本概念
- 2.priority_queue基本结构
- 3.size()成员函数
- 4.empty()成员函数
- 5.top()成员函数
- 6.push()成员函数
- 7.pop()成员函数
- 8.构造函数
- 9.完整代码
🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【C++的学习】
📝📝本篇内容：priority_queue基本概念；priority_queue基本结构；size()成员函数；empty()成员函数；top()成员函数；push()成员函数；pop()成员函数；构造函数；完整代码
⬆⬆⬆⬆上一篇：C++模拟实现queue
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-
1.priority_queue基本概念
priority_queue是我们常说的优先级队列，是一个容器适配器，它底层默认使用了vector容器，并且在此基础上使用了堆算法。因为牵扯到了堆，那就跟二叉树搭上了点关系。我们的二叉树中有一种树叫做完全二叉树，什么是完全二叉树呢？
完全二叉树：前N-1层是满的，最后一层可以不满，但是必须从左往右是连续的。要注意的是满二叉树是一种特殊的完全二叉树
根据它的这个特性（没有任何节点漏洞），我们可以将完全二叉树存储到数组中，在C++中我们就可以把它放入vector中，这种将数组的方式来表述tree称为隐式表述法
那么任何一个节点求它的父节点以及左右子节点公式如下：
若i>0,i位置结点的双亲序号：（i-1）/2=parent；i=0，i为根节点编号，无双亲结点
设n为数组的大小，若2i+1<n,左孩子序号：2i+1=leftchild；2i+1>=n否则无左孩子
设n为数组的大小，若2i+2<n,右孩子序号：2i+2=rightchild；2i+2>=n否则无右孩子
前面说了堆算法是建立在树上的，那么什么是堆呢？
我们的堆分为两种，大根堆或者是小根堆
大堆：树中所有的父亲都大于等于孩子
小堆：树中的所有父亲都小于等于孩子
优先级队列只能在底端加入元素，从顶端取出元素，这也是为什么是队列原因，并且我们取出的值是所有元素中最大的或者最小的（优先队列中位于顶部的元素)
2.priority_queue基本结构
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
namespace lnb
{
//用来比较的仿函数
template<class T>
struct less
{
bool operator()(const T& x,const T& y)const
{
//less是<,greater是>
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)const
{
return x > y;
}
};
template<class T, class Container=vector<T>, class Compare=less<T>>
class priority_queue
{
public:
private:
Container _con;//用来存储完全二叉树
Compare _com;//用来比较的方法
};
}
3.size()成员函数
//有效元素个数
size_t size()const
{
return _con.size();
}
4.empty()成员函数
//判空
bool empty()const
{
return _con.empty();
}
5.top()成员函数
//获取最大或最小的元素（位于顶部，即下标为0的元素）
const T& top()const
{
return _con[0];
}
所获取的值如上图
6.push()成员函数
void push(const T& val)
{
//1.先进行插入
_con.push_back(val);
//2.进行向上调整
AdjustUp(_con.size()-1);
}
private:
void AdjustUp(int child)
{
//1.先找到父节点
int parent = (child - 1) / 2;//公式前面讲过
while (child > 0)//保证不超过根节点，最后一次循环只能是child为1或2，parent为0
{
//2.判断是否父节点小于(大于)孩子节点
//if(Compare()(_con[parent],_con[child]))//使用匿名对象来判断也可以
if (_com(_con[parent], _con[child]))//默认是大堆，是判断是否父节点小于孩子节点
{
//3.进行交换
swap(_con[parent], _con[child]);
//4.调整parent，child,继续向上调整直到不需要调换或者到根节点
child = parent;//父节点成为孩子节点继续往上调整
parent = (child - 1) / 2;
}
else
{
//已经不需要调整了
break;
}
}
}
当把元素插入后，只需要进行一个向上调整即可，我们默认是大堆哈，这是为了保证当我们大堆的一个结构，所有的父结点大于孩子节点。因此插入的一个元素需要进行调整，如果它大于自己的父结点，就往上调整和父节点进行交换，孩子节点就到了父节点的位置，然后继续向上调整直到父节点大于孩子节点或者调整到根节点结束
上面的代码中，我们使用到了仿函数来进行判断，但是我们如果没有它呢？那么对于泛型编程是一个巨大的问题，使用者无法通过外部的模板参数来控制内部的比较，只能通过直接的><来判断。
7.pop()成员函数
void pop()
{
//1.删除的是最大（最小）的元素，所以先将_con[0]和_con[_con.size()-1]交换
swap(_con[0], _con[_con.size() - 1]);
//2.容器进行尾删
_con.pop_back();
//3.交换后，就可以将_con[0]向下调整
AdjustDown(0);
}
private:
//向下调整
void AdjustDown(int parent)//默认为大堆
{
//1.先求出左孩子节点
int child = parent * 2 + 1;
while (child < _con.size())//保证孩子节点不会超过容器的大小
{
//2.保证大（小）根堆的特性，选出孩子节点中较大（小）的那个
if (child+1<_con.size()&&_com(_con[child],_con[child + 1]))//确保右孩子的存在
{
child++;
}
//3.进行判断是否父节点小于（大于）孩子节点
if (_com(_con[parent], _con[child]))
{
//4.进行交换
swap(_con[parent], _con[child]);
//5.孩子节点成为父节点，并重新找左孩子节点
parent = child;
child = parent * 2 + 1;
}
else
{
//父节点大于（小于）孩子节点即可结束
break;
}
//6.一直调整，直到父节点大于（小于）孩子节点或者父节点没有孩子节点了
}
}
上面已经给出了代码和交换的图片，我们首先来讲一下为什么需要通过交换才能删除这个最大（最小）元素，究其原因还是它在根节点的原因，没有办法对它进行一个直接删除，一旦直接删除，就会导致整体的一个堆结构就乱掉了，那么最好的方法就是和尾元素进行交换，然后进行向下调整，这样不但保证了结构的完整性，效率还高
向上调整如下图:
8.构造函数
//使用迭代器构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first,last)
{
//完全混乱的结构，需要进行调整
//第一个-1是找到最后一个元素，第二个-1是为了找到父节点
int end = ((_con.size() - 1) - 1) / 2;//找到最后一个元素的父节点
while (end >= 0)//直到调整到根节点
{
AdjustDown(end);//对于子树进行从下往上挨个进行向下调整
end--;
}
}
//默认构造函数
priority_queue()
{
}
默认构造就没什么好讲的，主要是使用迭代器构造，这个也是一个难点，给一堆混乱的数据，如何变成符合堆特性
想要保证一组毫无序列的元素变成堆，就需要保证每一个子树的父节点都大于（小于）孩子节点，因此我们只能从最后一棵子树开始向下调整，这样当调整到上一层时，下层都已经是堆了，只需要对当前节点也是向下调整即可。一直到根节点完成最后一次向下调整就可以完成堆的构建。
9.完整代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
namespace lnb
{
//用来比较的仿函数
template<class T>
struct less
{
bool operator()(const T& x,const T& y)const
{
//less是<,greater是>
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)const
{
return x > y;
}
};
template<class T, class Container=vector<T>, class Compare=less<T>>
class priority_queue
{
public:
//使用迭代器构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first,last)
{
//完全混乱的结构，需要进行调整
//第一个-1是找到最后一个元素，第二个-1是为了找到父节点
int end = ((_con.size() - 1) - 1) / 2;//找到最后一个元素的父节点
while (end >= 0)//直到调整到根节点
{
AdjustDown(end);//对于子树进行从下往上挨个进行向下调整
end--;
}
}
//默认构造函数
priority_queue()
{
}
//有效元素个数
size_t size()const
{
return _con.size();
}
//判空
bool empty()const
{
return _con.empty();
}
//获取最大或最小的元素（位于顶部，即下标为0的元素）
const T& top()const
{
return _con[0];
}
void push(const T& val)
{
//1.先进行插入
_con.push_back(val);
//2.进行向上调整
AdjustUp(_con.size() - 1);
}
void pop()
{
//1.删除的是最大（最小）的元素，所以先将_con[0]和_con[_con.size()-1]交换
swap(_con[0], _con[_con.size() - 1]);
//2.容器进行尾删
_con.pop_back();
//3.交换后，就可以将_con[0]向下调整
AdjustDown(0);
}
private:
//向下调整
void AdjustDown(int parent)//默认为大堆
{
//1.先求出左孩子节点
int child = parent * 2 + 1;
while (child < _con.size())//保证孩子节点不会超过容器的大小
{
//2.保证大（小）根堆的特性，选出孩子节点中较大（小）的那个
if (child+1<_con.size()&&_com(_con[child],_con[child + 1]))//确保右孩子的存在
{
child++;
}
//3.进行判断是否父节点小于（大于）孩子节点
if (_com(_con[parent], _con[child]))
{
//4.进行交换
swap(_con[parent], _con[child]);
//5.孩子节点成为父节点，并重新找左孩子节点
parent = child;
child = parent * 2 + 1;
}
else
{
//父节点大于（小于）孩子节点即可结束
break;
}
//6.一直调整，直到父节点大于（小于）孩子节点或者父节点没有孩子节点了
}
}
void AdjustUp(int child)
{
//1.先找到父节点
int parent = (child - 1) / 2;//公式前面讲过
while (child > 0)//保证不超过根节点，最后一次循环只能是child为1或2，parent为0
{
//2.判断是否父节点小于(大于)孩子节点
//if(Compare()(_con[parent],_con[child]))//使用匿名对象来判断也可以
if (_com(_con[parent], _con[child]))//默认是大堆，是判断是否父节点小于孩子节点
{
//3.进行交换
swap(_con[parent], _con[child]);
//4.调整parent，child,继续向上调整直到不需要调换或者到根节点
child = parent;//父节点成为孩子节点继续往上调整
parent = (child - 1) / 2;
}
else
{
//已经不需要调整了
break;
}
}
}
private:
Container _con;//用来存储完全二叉树
Compare _com;//用来比较的方法
};
}
🌸🌸C++priority_queue模拟实现的知识大概就讲到这里啦，博主后续会继续更新更多C++的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪