//使用示例
#include<iostream>
#include<queue>
using namespace std;
//這是自定義優(yōu)先級的一種格式
template<typename T>
class gt
{
public:
	//如果返回true則b優(yōu)先，返回false則a優(yōu)先，所以這里使用gt會生成小堆
	bool operator()(T a, T b)
	{
		return a > b;
	}
private:
};
int main()
{
	priority_queue<int> heap1;//int表示儲存的類型
	priority_queue<int, vector<int>> heap2;//這里vector表示使用的底層容器，這里也可以換成deque<int>。
	
	//greater為編譯器提供的類模板，默認的優(yōu)先級是大堆，而使用它可以生成小堆。
	priority_queue<int, vector<int>, greater<int>> heap3;

	//當然也可以自己設(shè)計一個優(yōu)先級方式傳入，該方法常常用于儲存自定義類型，而內(nèi)置類型編譯器提供的就夠用。
	priority_queue<int, vector<int>, gt<int>> heap4;

	//push接口用于存入元素
	heap4.push(2);
	heap4.push(7);
	heap4.push(1);
	heap4.push(5);
	cout << heap4.size() << endl;//size用于計算隊列中元素的個數(shù)
	while (!heap4.empty())//empty用于判斷隊列是否為空
	{
		cout << heap4.top() << ' ';//top獲取隊頭元素
		heap4.pop();//pop刪除隊頭元素
	}
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;
namespace byte//用命名空間限制它的作用域，來區(qū)別于庫里面的優(yōu)先級隊列
{
	template<typename T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		//...
	private:
		//...
	};
}

private:
	Container arr;
	Compare comp;

#include<iostream>
#include<vector>
using namespace std;
namespace byte
{
	template<typename T>
	class less
	{
	public:
		//如果返回true則b優(yōu)先，返回false則a優(yōu)先，所以這里使用gt會生成小堆
		bool operator()(T a, T b)
		{
			return a < b;
		}
	private:
	};
	template<typename T>
	class greater
	{
	public:
		//如果返回true則b優(yōu)先，返回false則a優(yōu)先，所以這里使用gt會生成小堆
		bool operator()(T a, T b)
		{
			return a > b;
		}
	private:
	};

	template<typename T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:

		void AdjustUP()
		{
			int child = arr.size() - 1, father = (child - 1) / 2;
			while (child > 0)
			{
				if (comp(arr[father], arr[child]))
				{
					std::swap(arr[child], arr[father]);
					child = father;
					father = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDOWN()
		{
			int father = 0, child = father * 2 + 1;
			while (child < arr.size())
			{
				if (child + 1 < arr.size() && comp(arr[child], arr[child + 1]))
				{
					child++;
				}
				if (comp(arr[father], arr[child]))
				{
					std::swap(arr[child], arr[father]);
					father = child;
					child = father * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(T x)
		{
			arr.push_back(x);
			AdjustUP();
		}
		void pop()
		{
			std::swap(arr[0], arr[arr.size() - 1]);
			arr.pop_back();
			AdjustDOWN();
		}
		T top()
		{
			return arr[0];
		}
		size_t size()
		{
			return arr.size();
		}
		bool empty()
		{
			return arr.size() == 0;
		}
	private:
		Container arr;
		Compare comp;
	};
}