一. 简介

priority_queue是 C++ 标准模板库（STL）中的容器适配器，用于实现优先队列这一特殊数据结构。优先队列中的元素会按照优先级排序，每次取出的都是优先级最高的元素， 它的底层实现通常采用 堆（heap）数据结构。

在 C++ 中，priority_queue模板类定义在**queue** 头文件中。我们可以通过指定元素类型和比较函数（如函数指针、函数对象或 Lambda 表达式），来创建不同排序规则的优先队列。需要注意的是：默认情况下，priority_queue使用std::less作为比较函数，使得元素优先级按从大到小的顺序排列（即默认是 “大堆”）；若需元素按从小到大的顺序排列，则可改用std::greater作为比较函数。

less 排大堆
greater 排小堆

二. 使用

priority_queue支持以下操作：

• empty (): 检测容器是否为空
• size (): 返回答器中有效元素个数
• top ():返回优先级队列中最大（最小）元素，即堆顶元素
• push_back (): 在容器尾部插入元素
• pop_back (): 删除容器尾部元素

要使用priority_queue，需要包含头文件。

#include<queue>

int main()
{
	priority_queue<int> pq;
	for (size_t i = 0; i < 5; i++)
	{
		pq.push(i);
	}
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

默认使用了less，所以排成了大堆

如果换成greater就变成小堆了

三. priority_queue函数模拟实现

底层是使用仿函数和堆实现的

template<class T>
class Less         //仿函数
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Great
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};


namespace ncs
{
	template<class T, class container = vector<T>,class compare = Less<T>>   //大堆用的小于，小堆用大于
	class priorityqueue
	{
	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 = parent * 2 + 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 = parent * 2 + 1;
				}
			
				else
				{
					break;
				}

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

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

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


	private:
		container _con;

	};

}