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;
	//默认是最大的，因为我们默认参数给的是Less
	rens::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;
}