优先级队列的基本使用

模拟实现上面的接口函数，优先级队列不是队列，而是类似一个堆一样的东西，我们先来试试它的接口函数是怎么个样子的。

 需要包含的头文件是queue。

 

#include<iostream>
#include<queue>
using namespace std;
void priority_queuetest1()
{
	priority_queue<int> pq;
	pq.push(2);
	pq.push(1);
	pq.push(4);
	pq.push(3);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}

}
int main()
{
	priority_queuetest1();
	return 0;
}

这就是我们的基本使用方法，但是我们运行我们的代码之后发现的打印结果不是升序的

打印结果· ： 4 3 2 1

这里就要说明一个问题，我们建立的堆是大堆，也就导致了最后的打印结果就是降序，这个地方会出现一个叫仿函数的东西，我们在后面进行模拟实现的时候回来看到这个。

需要记住小于是大堆，大于是小堆！！！！（后面会解释）

我们的sort排序也是这个样子的。

如果我们用sort对我们的排序要进行排序的时候，默认是升序，原因就是我们进行传仿函数的时候传的是less，我们可以来看看sort的文档。

 

这里我们传的就是一个对象，而上面的优先级队列传的不是对象，而是模板参数，这里需要注意一下，我们假如要排一个 vector的升序。代码如下。

	vector<int> v = { 6,5,4,3,2,1 };
	sort(v.begin(), v.end());
	for (auto e : v)
	{
		cout << e << " ";
	}

结果 ： 1 2 3 4 5 6

如果要排降序的话就需要传一个参数就是仿函数过去。准确来说是对象，而我们上面的优先级队列是类型，编译器会自动去推算！！！！

使用如下

vector<int> v = { 6,5,4,3,2,1 };
	sort(v.begin(), v.end(),greater<int>());
	for (auto e : v)
	{
		cout << e << " ";
	}

 6  5  4  3  2  1

 那如果我们要进行的是小堆呢，就可以这样使用。

void priority_queuetest1()
{
	priority_queue<int,vector<int>,greater<int>> pq;
	pq.push(2);
	pq.push(1);
	pq.push(4);
	pq.push(3);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}

	/*vector<int> v = { 6,5,4,3,2,1 };
	sort(v.begin(), v.end(),greater<int>());
	for (auto e : v)
	{
		cout << e << " ";
	}*/


}

这里C语言和C++的区别 ，C语言是没有仿函数的，他是用函数指针来进行调用的。比如qsort函数就是这样的。

仿函数

1 ：仿函数其实就是一个类，只要我们在类里面重载了运算符括号，这个类我们就可以认定为具有仿函数功能！

2 ： 它的对象可以像函数一样去调用。

3 ： 写成模板的时候，那么我们任意数据都可以来进行使用。

那如果我们要写一个最基本的仿函数是怎么个样子，首先就是它得是一个类，是不是要写成模板，取决于你自己。

void priority_queuetest2()
{

	
	struct Less//区别于库里面
	{
		bool operator()(const int& x, const int& y)
		{
			return x < y;
		}
	};
	Less com;
	cout << Less()(1, 2) << endl;
	cout << com(5, 2) << endl;
	cout << com.operator()(3,1) << endl;
}

 模拟实现队列

我们先实现一个不加上仿函数的优先级队列，根据文档里的接口先来实现一些push， 我们的堆是怎么进行push的呢？？

因为我们的堆其实就是一个满二叉树的结构，那在数组里其实就是尾插进去一个数，但是尾插进去之后，可能就不是满二叉树了，所以要做的就是向上调整。

优先级队列的插入push

void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}

push的之后就需要进行向上调整，在这里我们是用了其他容器来进行实现的，因为二叉树是共和数组，所以这里的默认容器就是vector。

需要进行的是向上调整，在我的文章堆里面是讲过这个的，大家可以跳转到下面的这个链接当中

https://blog.csdn.net/2301_76895050/article/details/134611394?spm=1001.2014.3001.5501

向上调整

void adjust_up(size_t child)
		{
			size_t 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，我们需要注意的是pop不是pop尾部的数据，而是数组下标是0位置二的，我们只需要先交换头和尾位置的数据，然后再进行删除，这个时候把头部的数据删掉了，但是却不是二叉树，这个时候（默认是大堆）堆顶的数据不是最大的，所以需要做的就是向下进行调整。

优先级队列的pop

void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

向下调整

void adjust_down(size_t parent)
		{
			size_t child = 2 * parent + 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 = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

其他接口函数都是对我们的容器进行一个封装，所以大体框架就是下面的这个

template<class T,class Container = vector<T>>
	class priority_queue
	{
	public:
		//默认是大堆
		void adjust_up(size_t child)
		{
			size_t 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;
				}
				
			}
			
		}
		void adjust_down(size_t parent)
		{
			size_t child = 2 * parent + 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 = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
		T top()
		{
			return _con[0];
		}


	private:
		Container _con;
	};

写完一个代码就需要进行测试一下，我们可以插入一下数据，看看是不是大堆，然后打印我们的数据，来看看是不是有序的就行了、

测试代码

void priority_queuetest1()
	{
		priority_queue<int> pq;
		pq.push(5);
		pq.push(2);
		pq.push(1);
		pq.push(4);
		pq.push(3);
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
	}

检查我们的代码的时候其实是可以先来看插入的逻辑的，看看插入之后是不是建立成大堆，如果建立堆问题出错了，就只要两个地方会有问题，一个就是我们插入逻辑，插入逻辑一般不会有问题的，可能再传参数的地方有问题，还有就是我们的向上调整是不是存在一些逻辑问题。

重新认识仿函数

如何控制比较逻辑呢，我们这里默认建立的是大堆，我们需要通过仿函数来进行更改比较逻辑，仿函数最大逻辑就是，对象可以像函数那样进行比较。

快速实现仿函数。

	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>
	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
	{
	public:
		//默认是大堆
		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
				
			}
			
		}
		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
				{
					child++;
				}
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
		T top()
		{
			return _con[0];
		}


	private:
		Container _con;
	};
	void priority_queuetest1()
	{
		priority_queue<int> pq;
		pq.push(5);
		pq.push(2);
		pq.push(1);
		pq.push(4);
		pq.push(3);
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
	}

优势1 ： 只要更改仿函数就能更改我们的比较逻辑 大堆也就变成小堆

优势2 ： 是一个类，理解起来和写起来都比较方便，c语言要实现这样只能通过函数指针，函数指针是个比较麻烦的东西

完整代码

namespace tjl
{

	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
	{
	public:
		//默认是大堆
		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
				
			}
			
		}
		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
				{
					child++;
				}
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
		T top()
		{
			return _con[0];
		}


	private:
		Container _con;
	};
	void priority_queuetest1()
	{
		priority_queue<int,vector<int>,greater<int>> pq;
		pq.push(5);
		pq.push(2);
		pq.push(1);
		pq.push(4);
		pq.push(3);
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
	}
}

 补充

仿函数的作用可不只是这样嗷，我们如果要来比较一下我们的日期应该是怎么来实现呢。

	class Date
	{
	public:
		friend ostream& operator<<(ostream& _cout, const Date& d);

		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);
		}
	private:
		int _year;
		int _month;
		int _day;
	};

	ostream& operator<<(ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}

这个时候因为我们假设比较Date，当然我们日期也可以使用之前的方式来进行比较，这是这个时候的比较类型是自定义的。

代码如下

 

void priority_queuetest2()
	{
		priority_queue<Date> pq;
		pq.push({2023,1,3});
		pq.push({2013,1,7});
		pq.push({2034,3,1});
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
	}

但是如果我们现在要进行的是Date*的比较呢，这个时候就不可了，首先比较的时候重载必须是自定义的类型，内置类型是不能进行重载的，比较逻辑就是不正确的，所以这个时候要在写一个仿函数

class GreaterPDate
	{
	public:
		bool operator()(const Date* p1, const Date* p2)
		{
			return *p1 > *p2;
		}
	};

以上就是今天的分享，我们下篇文章再见!!!