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;//用来比较的方法};}