c++中priority_queue的应用及模拟实现

1.介绍

priority_queue 是一种数据结构，它允许你以特定的顺序存储和访问元素。在 C++ 标准模板库（STL）中，priority_queue 是一个基于容器适配器的类模板，它默认使用 std::vector 作为底层容器，并且默认使用最大堆来存储元素。priority_queue 中的元素按照优先级顺序排列。默认情况下，优先级最高的元素（即值最大的元素）位于队列的顶部。访问时，只能访问优先级最高的元素（即队列顶部的元素），不能直接访问其他元素。

2.代码体验

测试代码：

#include<vector>
#include<queue>	
#include<iostream>
using namespace std;
int main()
{priority_queue<int> pq;pq.push(20);pq.push(5);pq.push(60);pq.push(80);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

运行结果如下：

结果证明，元素确实是按大根堆的形式存储的！

3.自定义比较函数

priority_queue除了直接用于排序元素之外，还能用于自定义比较函数，来改变元素的优先级顺序例如，如果你想让优先队列按照元素的某个属性排序，可以定义一个比较函数

代码示例：

class date
{friend ostream& operator<<(ostream& _cout, const date& d);
public:date(int year=2025,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);}
private:int _year;int _month;int _day;
};
ostream& operator<<(ostream& _cout, const date& d)
{_cout << d._year << " " << d._month << " " << d._day;return _cout;
}int main()
{priority_queue<date, vector<date>, greater<date>> q1;//解释一下这里为什么要写三个参数，而之前的应用为什么写一个参数就可：//这是由于priority_queue的模板就是这样给的，（详见下方图片），由于我们要进行//日期的某种排序，需要把第三个参数写上，而c++规定，你要写第三个参数 前面的第二个就必须写//所以我们第二个参数要写上！q1.push(date(2025, 1, 27));q1.push(date(2024, 10, 6));q1.push(date(2025, 5, 8));while (!q1.empty()){cout<< q1.top()<<endl;q1.pop();}return 0;
}

 

运行结果如下：

那个比较函数我们也可以自己来写，也支持的！

class date
{friend ostream& operator<<(ostream& _cout, const date& d);
public:date(int year=2025,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);}
private:int _year;int _month;int _day;
};
ostream& operator<<(ostream& _cout, const date& d)
{_cout << d._year << " " << d._month << " " << d._day;return _cout;
}
int main()
{priority_queue<date, vector<date>> q2;q2.push( date(2025, 1, 27));q2.push( date(2024, 10, 6));q2.push( date(2025, 5, 8));while (!q2.empty()){cout << q2.top() << endl;q2.pop();}return 0;
}

结果如下：

 

我们也可以写一个比较函数来进行比较

比较函数参数：

struct lessdate                          //自定义一个比较函数
{bool operator()(date* p1, date* p2){return *p1 < *p2;}
};

main函数也要变一下：

​
int main()
{priority_queue<date*, vector<date*>, lessdate> q2;q2.push(new date(2025, 1, 27));q2.push(new date(2024, 10, 6));q2.push(new date(2025, 5, 8));while (!q2.empty()){cout << *q2.top() << endl;q2.pop();}return 0;
}​

解释一下这里为什么要new一下，我们的q2是指针， 存储的是指针而不是对象，通过创建一个对象，并将其地址推入q2中，所以要new一下，此外，我们还要加一个比较函数，如果不加直接比的话，就是按照地址的大小来确定输出了，而与输入内容的大小无关了！

注：若比较函数参数不是指针，而是date p1,date p2，那main函数就不需要new date了！ 

4.模拟实现priority_queue

 由于其默认使用最大堆来存储元素，因此我们在模拟实现时2，务必要涉及到堆的相关算法，如向上调整算法以及向下调整算法，如有遗忘可以找我之前的博客看一下，在本篇我也会略作讲解

1）基本框架：

#include<vector>
namespace rens
{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 ,class compare>class priority_queue{public:private:container _con;};
}

插入数据：和二叉树，堆一样，先将插入的数据放在最下面的叶结点，在逐步向上调整，以达到最大堆的结构 

删除数据：不要直接将最上面的删去，这样会造成这棵树“辈分混乱、群龙无首”，应先将最上面的数与最后一个数据交换，在向下调整，调整完毕后，删去最后一个数据

整体代码实现：

#include<vector>
#include <iostream>
namespace rens
{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(size_t child){compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);          //我们要排大堆，大的往上走child = parent;parent = (child - 1) / 2;}else {break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//先找最小孩子if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T&  top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:container _con;};
}

代码测试：

#include"priority_queue.h"
#include<iostream>
using namespace std;
//小的优先级高int main()
{cout << "升序" << endl;rens::priority_queue<int, std::vector<int>, rens::greater<int>> pq;pq.push(2);pq.push(5);pq.push(4);pq.push(1);pq.push(50);while (!pq.empty()){std::cout << pq.top()<<" ";pq.pop();}cout << endl << "降序"<<endl;//默认是最大的，因为我们默认参数给的是Lessrens::priority_queue<int, std::vector<int>> pq1;pq1.push(2);pq1.push(5);pq1.push(4);pq1.push(120);pq1.push(1);while (!pq1.empty()){cout << pq1.top()<<" ";pq1.pop();}cout << endl;return 0;
}

5.仿函数

 在 C++ 中，仿函数（Functor）是一种重载了函数调用操作符 operator() 的类或结构体。仿函数可以像函数一样被调用，但它们实际上是对象。仿函数通常用于定义特定行为，它们可以被传递给算法，如 std::sort 或 std::for_each，以自定义这些算法的行为。

#include<vector>
#include <iostream>
namespace rens
{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};
}
bool lessfunc(int x, int y)
{return x < y;
}
int main()
{bool (*ptr)(int, int) = lessfunc;rens::less<int> lessfunc;cout << lessfunc(1, 2) << endl;
}