C++初阶：STL详解（十）——priority_queue的介绍，使用以及模拟实现

✨✨小新课堂开课了，欢迎欢迎~✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：C++：由浅入深篇

小新的主页：编程版小新-CSDN博客

一.priority_queue的介绍

优先级队列被实现为容器适配器，容器适配器就是将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部，并且它的第一个元素总是它所包含的元素中最大的。因为默认情况下priority_queue是大堆。

底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器支持随机访问迭代器访问，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

二.priority_queue的使用

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

注意：默认情况下priority_queue是大堆。

 2.1priority_queue的定义

1.指定定义：

//指定定义
//1.以vector作为底部容器类，内部构建大堆结构
priority_queue<int, vector<int>, less<int>> pq1;

//2.以vector作为底部容器类，内部构建小堆结构
priority_queue<int, vector<int>, greater<int>> pq2;

2.未指定定义：

//未指定定义
priority_queue<int> pq3;//默认以vector作为底层容器类，内部构建大堆结构

2.2priority_queue的常见操作 

void priority_queue1()
{
	priority_queue<int> pq1;
	pq1.push(3);
	pq1.push(7);
	pq1.push(2);
	pq1.push(5);
	pq1.push(8);
	pq1.push(1);
	pq1.push(6);
	pq1.push(4);//插入

	while (!pq1.empty())
	{
		cout << pq1.top()<<" ";//返回堆顶元素
		pq1.pop();//删除堆顶元素
	}
	
	//8 7 6 5 4 3 2 1
}

三.priority_queue的模拟实现

我们在模拟实现priority_queque之前，要先复习一下两个堆算法，这里我们就以构建大堆结构为例。

3.1向上调整建堆

以大堆为例，向上调整建堆就是在堆的末尾插入一个数据后，经过向上调整，依然是一个大堆。

调整思想：
1、将目标结点与其父结点进行比较。
2、若目标结点的值比其父结点的值大，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整，直到目标节点的值比其父节点的值小位置位置，调整完毕。

3.2向下调整建堆

以大堆为例，向下调整算法是为了删除堆顶数据，在删除堆顶数据后，让该堆依旧是大根堆。

调整思想：
1、将目标结点与其较大的子结点进行比较。
2、若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整，直到目标节点比其较大的子节点的值大为止，调整完成。

3.3priority_queue的模拟实现

namespace fu
{
	//内部构建大根堆
	template <class T>
	struct less
	{
		bool opeartor()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	//内部构建小跟堆
	template <class T>
	struct greater
	{
		bool opeartor()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	//优先级队列模拟实现
	template<class T, class Container = vector<int>, class Compare = less<T>>
	class priority_queue
	{
	public:
		//向上调整建堆
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;

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

		//插入数据
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(x);
		}

		//向下调整建堆
		void AdjustDown(int n, int parent)
		{
			int child = 2 * parent + 1;
			while (child < n)
			{
				if (child + 1 < n && _comp(_con[child], _con[child + 1]))
				{
					child++;
				}

				if (_com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

		//删除数据
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(_con.size(),0);
		}

		//访问堆顶元素
		T& top()
		{
			return _con[0];
		}

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

		//返回有效元素个数
		size_t size() 
		{
			return _con.size();
		}
		//判断队列是否为空
		bool empty() 
		{
			return _con.empty();
		}

	private:
		Container _con;
		Compare _com;
	};
}

感谢各位大佬的观看，创作不易，还请各位大佬支持~