【C++】优先级队列priority

> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等

> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：能手撕仿函数模拟

> 毒鸡汤：你活得不快乐的原因是：既无法忍受目前的状态，又没能力改变这一切。

> 望小伙伴们点赞👍收藏✨加关注哟💕💕 

🌟前言

我们在vector讲解中已经了解到了priority_queue，只能说是浅谈，priority_queue底层到底是个啥勒？今天带大家揭晓它的面纱。

⭐主体

这里就创建两个文件priority_queue.h（头文件），test.cpp（测试代码文件）

咱们按照下面图解来学习今天的内容：

🌙什么是priority_queue

优先级队列priority_queue，即数据结构中的堆，堆是一种通过使用数组来模拟实现特定结构二叉树的二叉树的数据结构，根据父亲节点与孩子节点的大小关系，可以将堆分为大堆和小堆：

大堆：所有父亲节点的值都大于或等于它的孩子节点的值。

小堆：所有父亲节点的值都小于或等于它的孩子节点的值。

在C++ STL中，priority_queue的声明为：template  class priority_queue;

其中，每个模板参数的含义为：

• T：优先级队列中存储的数据的类型
• Container：用于实现优先级队列的容器，默认为vector
• Comapre：比较仿函数，用于确定是建大堆还是建小堆。Compare默认为std::less，建大堆，如果要建小堆，需要显示传参std::greater，同时还有显示的声明容器类型。

  

  🌙priority_queue常见接口的使用

  1. 优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素是所有元素中最大的。
  2. 优先级队列的底层是用堆进行实现的，大根堆的堆顶是最大的。
  3. 标准容器vector和queue都满足以上要求，如果没有特定要求，默认使用vector作为底层容器类。
  4. 需要支持随机访问迭代器，保证内部始终保持堆结构。容器适配器在需要的时候调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
  5. 优先级队列的底层容器可以使任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
  • empty()：检测容器是否为空。
  • size()：返回容器有效元素个数。
  • front()：返回容器第一个元素的引用
  • push_back()：在容器尾部插入元素
  • pop_back()：删除容器尾部元素

    使用priority_queue：

    #include
    #include
    #include
    int main()
    {
    	std::priority_queue maxHeap;   //建大堆
    	int data[10] = { 56,12,78,23,14,34,13,78,23,97 };
    	//让arr中的数据依次入大堆
    	for (int i = 0; i  0)
    			{
    				//if (_con[child] > _con[parent])->父亲小于孩子就调整
    				if (com(_con[parent], _con[child]))//
    				{
    					swap(_con[child], _con[parent]);
    					child = parent;
    					parent = (child - 1) / 2;
    				}
    				else
    					break;
    			}
    		}
    		void AdjustDown(size_t parent)
    		{
    			size_t child = parent * 2 + 1;
    			while (child  _con[child])
    				if (child + 1  _con[parent])
    				if (com(_con[parent], _con[child]))
    					swap(_con[parent], _con[child]);
    				else
    					break;
    				parent = child;
    				child = parent * 2 + 1;
    			}
    		}
    	public:
    		// 默认构造函数
    		priority_queue()
    		{}
    		// 通过迭代器区间的构造函数
    		template
    		priority_queue(InputIterator first, InputIterator last)
    			:_con(first, last)
    		{
    			size_t lastchild = size() - 1;
    			size_t parent = (lastchild - 1) / 2;
    			for (size_t i = parent; i >= 0; i--)
    			{
    				AdjustDown(i);
    			}
    		}
    		void push(const T& x)
    		{
    			_con.push_back(x);
    			AdjustUp(size() - 1);
    		}
    		void pop()
    		{
    			swap(_con[size() - 1], _con[0]);
    			_con.pop_back();
    			AdjustDown(0);
    		}
    		size_t size() const
    		{
    			return _con.size();
    		}
    		T& top()
    		{
    			return _con[0];
    		}
    		bool empty()
    		{
    			return _con.empty();
    		}
    	private:
    		Container _con;
    	};
    	void priority_test1()
    	{
    		priority_queue pq;
    		pq.push(40);
    		pq.push(30);
    		pq.push(56);
    		pq.push(26);
    		pq.push(45);
    		while (!pq.empty())
    		{
    			cout