c++系列之priority_queue的模拟实现

💗 💗 博客:小怡同学
💗 💗 个人简介:编程小萌新
💗 💗 如果博客对大家有用的话，请点赞关注再收藏 🌞

priority_queue的介绍

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。//默认情况下priority_queue是大堆

priority_queue的定义

priority_queue<T,vector,less>q1 //less是大堆
priority_queue<T,vector,greater> q1 //greater是小堆
priority_queue q1 //默认是大堆

priority_queue常用接口

push() 插入元素到队尾
pop() 弹出堆顶元素
top() 访问堆顶元素
size() 获取堆中元素
empty() 判断堆是否为空
swap() 交换两个队列的内容

priority_queue的模拟实现

向上调整算法

void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if(_comp(_con[parent], _con[child]))//仿函数比较大小
				{
					swap(_con[child], _con[parent]);
						child = parent;
						parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

向下调整算法

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

					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
		
			}
		}

priority_queue的模拟实现代码

#include <iostream>
#include <vector>
using namespace std;


namespace zjy
{
		
	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 = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if(_comp(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
						child = parent;
						parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
	
		void AdjustDown(int n, int parent)
	  	{
			int child = parent * 2 + 1;
			
			while (child < n)
			{
				if (child + 1< n && _comp(_con[child],_con[child+1]))
				{
					child++;
				}
				if(_comp(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);

					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
		
			}
		}
		void Pop()
		{
			swap(_con[0], _con[_con.size() - 1]);

			_con.pop_back();
			AdjustDown(_con.size(),0);//数组数量
		}
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}

		T& top()
		{
			return _con[0];
		}

		const T& top() const
		{
			return _con[0];
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}


	private:
		Container _con;
		Compare _comp;
	};
};

int main()
{
	zjy::priority_queue<int> qu;
	qu.push(1);
	qu.push(3);
	qu.push(5);
	qu.push(8);
	qu.push(10);
	qu.push(15);
	cout << qu.top() << endl;
	qu.Pop();
	qu.Pop();
	cout << qu.top() << endl;
	return 0;
}

运行结果