C++——priority_queue模拟实现

目录

前言

一、优先级队列介绍

二、优先级队列实现

向上调整

向下调整

 三、仿函数

 总结

---

前言

上一篇文章我们讲了stack和queue，这两个容器是容器适配器，本质上是一种复用，那本篇文章要讲的优先级队列也是一个容器适配器，我们一起来看看吧！

---

一、优先级队列介绍

通过文档可以看到，优先级队列也是一个容器适配器，它的底层是vector，但是除了这个适配器以外还有一个模版参数，这个模版参数是干什么的呢？这个模版参数是去控制优先级的，控制大的优先级高，还是小的优先级高，这里就涉及到一个仿函数的概念，那我们待会把主体逻辑实现完后再来把这个仿函数给套上，这里需要注意的是，虽然优先级队列也带队列两个字，但是它已经不符合队列的特性了，还有双端队列deque也是，不符合队列的特性，优先级队列更加像堆，也就是顺序结构的二叉树

---

二、优先级队列实现

那就跟栈和队列是一样的，我们先搭出来一个基本框架

namespace hx
{template<class T, class Container = vector<T>>>class priority_queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}const T& top() const{return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

向上调整

那这里的push仅仅这么写肯定是不行的，因为我们要维持堆的结构的特性，大堆就是所有的父亲都大于或等于孩子，小堆是所有的父亲都小于或等于孩子，库里实现的默认是大堆，那我们也来跟着实现一个大堆，那插入完成后，这个孩子就得去向上调整，找到自己合适的位置，下面用一张图来解释

插入的那个位置就是孩子，然后定义一个父亲，当父亲还存在，就去判断父亲是否大于孩子，大就交换然后继续向上调，不大就结束

void AdjustUp(int child)
{int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

---

向下调整

pop也是不能直接把最后一个数据给删了，这样删除毫无意义，那删除的具体做法应该是什么呢，删除应该是删堆顶元素，但是又不能直接删，直接删堆就乱了，应该让最后一个元素与堆顶元素交换，再删除，然后再从堆顶开始去向下调整

 向下调整多了一个选孩子的过程，因为我们是大堆，那也就是要把大的那个孩子选出来，再进行交换，没有孩子了或者父亲大于孩子了就结束

void AdjustDown(int parent)
{int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && (_con[child] < _con[child + 1])){++child;}if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

我们默认是左孩子大，在循环条件这里，在向下调整之前我们就已经调用了pop_back，所以就这里的size求出来是没问题的，然后还有一个注意的点，我们要拿左孩子和右孩子去比，要先去判断右孩子在不在，右孩子存在且大于左孩子，再让child变成右孩子

---

 三、仿函数

那现在我们把大堆给实现好了，那如果要实现小堆也要再写一个吗？像list的迭代器那里，普通迭代器和const迭代器只有返回值不一样，写两份就太冗余了，在这里也是一样，小堆就是换个符号，其他的就要全写一份吗，肯定是不会的，那就要引入一个仿函数的概念，仿函数就是C语言中的函数指针，函数指针这个东西定义起来太复杂了，C++就引入了仿函数，那什么叫仿函数呢，就是重载了operator()的类，那我们来自己写一个仿函数试试

namespace hx
{template<class T>struct Less{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct Greater{bool operator()(const T& x, const T& y){return x > y;}};
}int main()
{hx::Less<int> ls;cout << ls(1, 2) << endl;hx::Greater<int> gt;cout << gt(1, 2) << endl;return 0;
}

ls对象先定义出来，ls(1, 2)就会被转化成ls.operator()(1, 2)，就调到了仿函数如果我们有自己比较大小的方式，我们就可以把我们的仿函数传进去给优先级队列用，也就是说仿函数是可以做到在外部去控制内部的，库里面的仿函数就是这两个，less和greater，是小写的，我们这里用了大写，跟库区分开，那我们把自己的代码套上仿函数

---

namespace hx
{template<class T>struct Less{bool operator()(const T& x, const T& y){return  x < y;}};template<class T>struct Greater{bool operator()(const T& x, const T& y){return  x > y;}};template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{private:void AdjustUp(int child){Compare _cmp;int parent = (child - 1) / 2;while (child > 0){if (_cmp(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){Compare _cmp;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _cmp(_con[child], _con[child + 1])){++child;}if (_cmp(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}public:priority_queue(){}void push(const T& val){_con.push_back(val);//向上调整AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//向下调整AdjustDown(0);}const T& top() const{return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

这里的Less就用我们自己写的，优先级队列是默认大堆，用Less，那小堆就是Greater，用Compare实例化出_cmp对象，在父亲和孩子比较以及向下调整选左右孩子的时候都用_cmp对象去调用了operator()

要注意的是Less比较的是小于<，这里和传参的顺序是有关系的，我们要把大的放在右边，_cmp(_con[parent], _con[child])，孩子大于父亲就交换，要满足<的顺序，就得把孩子放在右边，如果是小堆，那就用Greater，就是要父亲大于孩子才去交换，_cmp(_con[parent], _con[child])，greater是>，刚好父亲在左边，所以我们这么写是能满足需求的，就看外面传什么就可以

---

那这样是不是就能解决所有场景的问题呢？显然不是，我们把之前的日期类拿出来，在优先级队列里存储日期的指针

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);
private:int _year;int _month;int _day;
};

int main()
{hx::priority_queue<Date*> pq;pq.push(new Date(2025, 1, 9));pq.push(new Date(2025, 2, 9));pq.push(new Date(2025, 3, 9));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;return 0;
}

我们多次运行发现，好像每一次的结果都不一样啊，这里默认大堆应该是3月2月1月的，那为什么出现不一样的结果呢？首先我们要知道，在向上调整去比较孩子和父亲的大小时会用到仿函数，仿函数内部就会比较出两个日期的大小，而自定义类型不能用运算符，所以日期类需要重载运算符才可以，重载了之后，就可以去调用仿函数了，库里面的仿函数其实就是我们前面那样写的，那因为我们插入的是指针，那仿函数接收到的参数就是两个日期类的指针，所以我们比较的是指针的大小！！！才会导致每次的结果都不一样，那现在就需要我们自己来控制了，自己写一个仿函数传进去

struct LessDate
{bool operator()(const Date* px, const Date* py){return *px < *py;}
};

参数是指针，我们比较的是解引用之后的日期大小

	hx::priority_queue<Date*, vector<Date*>, LessDate> pq;pq.push(new Date(2025, 1, 9));pq.push(new Date(2025, 2, 9));pq.push(new Date(2025, 3, 9));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;return 0;
}

现在运行多次，结果也都是一样的！！！

 具体的每一步的调用逻辑是这样的，已经用箭头和步骤表明了，大家可以结合着图来理解

---

 如果不传仿函数，用我们自己写的Less，那大家可以看到，跟上一张图比，是没有步骤四的，在比较x < y这步，按F11是进不去的，就是因为这里比较的两个指针的大小，不是函数调用就进不去

---

 总结

本篇文章我们优先级队列，引出了仿函数，他替代的是C语言的函数指针，实现了更加灵活的调用方式，可以做到在外部控制内部的细节，在最后的日期类的那里因为涉及到多个类了，所以调用可能会比较复杂，大家没太看明白可以多看两遍，尤其是看看图，或者是去调试一下，按F11进去，看看会走到哪里，总之，仿函数也是非常重要的一部分，也会经常用，大家肯定是会越来越熟练的，如果大家觉得小编写的不错，可以给一个一键三连，感谢大家的支持！！！