前言：
在之前我们学的数据结构中，我们知道顺序表、链表、栈、队列、堆二叉树。但是在
C++中我们又对这些有了全新的认识，本篇博客来详细讲解什么是优先级队列。

优先级队列(priority_queue)

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过
   随机访问迭代器访问，并支持以下操作：
   empty()：检测容器是否为空
   size()：返回容器中有效元素个数
   front()：返回容器中第一个元素的引用
   push_back()：在容器尾部插入元素
   pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

---

优先级队列的接口

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

函数声明	接口说明
priority_queue()/priority_queue(first,last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

优先级队列：不管我是不是有序或者无序插入数据，都会按照有序的方式取出数据。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
using namespace std;
#include"Priority_queue.h"
int main()
{
	px::priority_quque<int, vector<int>, Less<int>>pq;
	pq.push(5);
	pq.push(1);
	pq.push(3);
	pq.push(8);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	std::priority_queue<int,vector<int>,Greater<int>>qq;
	qq.push(2);
	qq.push(5);
	qq.push(6);
	qq.push(1);
	while (!qq.empty())
	{
		cout << qq.top() << " ";
		qq.pop();
	}
	cout << endl;

	return 0;
}

---

什么是仿函数？

它的真名叫做：函数对象（Function Object）
仿函数 = 看起来像函数，实际上是个对象（类的实例）
平时调用函数是这样：

add(1, 2);

仿函数是把一个类对象，用 () 调用，假装成函数：

Add add;
add(1, 2);   // 看起来像函数，其实是对象在调用 operator()

就是一个类，里面重载了 operator()

struct Add
{
    int operator()(int a, int b)
    {
        return a + b;
    }
};

为什么叫 “仿” 函数？
因为它不是真函数，但用起来和函数一模一样。
→ 模仿函数 → 仿函数

---

实现priority_queue

思路：
priority_queue 底层是堆堆需要两个核心操作：
向上调整 AdjustUp → 插入用
向下调整 AdjustDown → 删除堆顶用

我要做一个可以切换比较规则的堆
Less 就是 小于比较
Greater 就是 大于比较
它们都重载 operator()，传入两个值，返回 bool
只需通过调用就可以随意建大小堆，有仿函数就不用写死，所以让仿函数帮我们比较，我们就不用运算符比较了。

AdjustUp 向上调整（插入用）
新元素插入到最后
不断和父亲比较
满足比较规则就交换
一直往上走到根节点
不满足就停止（堆已经平衡）

void AdjustUp(int child)
{
	compare co; // 创建比较对象
	int parent = (child - 1) / 2;

	while (child > 0) // 没到根节点就继续
	{
		if (co(_qe[parent], _qe[child])) // 父与子比较
		{
			swap(父, 子); // 交换
			child = parent; // 继续往上
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

AdjustDown 向下调整（删除堆顶用）
删除堆顶，先把最后一个元素换到堆顶
然后从堆顶往下调整
父亲有两个孩子
必须先找到更大 / 更小的那个孩子
再和父亲比较
满足规则就交换
继续往下走

void AdjustDown(int parent)
{
	size_t child = parent * 2 + 1; // 先找到左孩子
	compare co;
	
	while (child < _qe.size())
	{
		// 右孩子存在，且比左孩子更符合规则
		if (child + 1 < _qe.size() && co(_qe[child], _qe[child+1]))
			++child;

		// 父亲和孩子比较
		if (co(_qe[parent], _qe[child]))
		{
			swap(父,子);
			parent = child;
			child = parent*2+1;
		}
		else
			break;
	}
}

push 思路：
尾插
向上调整

void push(const T&x)
{
	_qe.push_back(x);
	AdjustUp(_qe.size()-1);
}

pop 思路：
堆顶和最后一个元素交换
删除最后一个元素
向下调整

void pop()
{
	swap(_qe[0], _qe.back());
	_qe.pop_back();
	AdjustDown(0);
}

top 思路：
堆顶就是第一个元素

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

总结：
priority_queue = 堆
堆必须实现 向上调整 + 向下调整
用 仿函数 控制大小堆，不写死比较符
底层用 vector 存储
对外提供标准接口：push /pop/top /empty/size

完整代码：

#pragma once
#include<vector>
//仿函数
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;  
	}
};

namespace px
{
	template<class T,class comtainer=vector<T>,class compare=Less<T>>
	class priority_quque
	{
		comtainer _qe;

	public:

		void AdjustUp(int child)
		{
			compare co;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (co(_qe[parent],_qe[child]))
				{
					swap(_qe[parent], _qe[child]);
					child = parent;
					parent = (child - 1) / 2;

				}
				else
				{
					break;
				}
			}
		}
		void AdjustDown(int parent)
		{
			size_t child = (parent * 2) + 1;
			compare co;
			
			while (child < _qe.size())
			{
				if (child + 1 < _qe.size() && co(_qe[child] ,_qe[child + 1]))
				{
					++child;
				}
				if (co(_qe[parent] , _qe[child]))
				{
					swap(_qe[child], _qe[parent]);
					parent = child;
					child= (parent * 2) + 1;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T&x)
		{
			_qe.push_back(x);

			AdjustUp(_qe.size() - 1);
		}
		void pop(){
			swap(_qe[0], _qe[_qe.size() - 1]);
			_qe.pop_back();
			AdjustDown(0);
		}

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

		size_t size() const
		{
			return _qe.size();
		}

		bool empty() const
		{
			return _qe.empty();
		}
	};
}