#pragma once
#include <iostream>
#include <queue>
#include "stack.h"
#include "queue.h"
using namespace std;

namespace fast
{
	//template<class T, class Container=vector<T>>
	//class priority_queue
	//{
	//public:
	//	void swap(T& x, T& y)
	//	{
	//		T tmp = x;
	//		x = y;
	//		y = tmp;
	//	}
	//	void adjust_up(int child)//新插入的数据下标为child
	//	{
	//		int parent = (child - 1) / 2;
	//		while (child > 0)
	//		{
	//			if (_con[child] < _con[parent])
	//			{
	//				swap(_con[child], _con[parent]);
	//				child = parent;
	//				parent = (child - 1) / 2;
	//			}
	//			else
	//			{
	//				break;
	//			}
	//		}
	//	}
	//	void adjust_down(int parent)
	//	//n表示数据个数(size())，parent默认为0
	//	{
	//		int child = parent * 2 + 1;
	//		while (child < size())
	//		{
	//			if (child + 1 < size() && _con[child + 1] < _con[child])
	//			{
	//				child++;
	//			}
	//			if (_con[child] < _con[parent])
	//			{
	//				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;
	//};
	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;
		}
	};

	template<class T, class Container=vector<T>, class Compare=less<int>>
	class priority_queue
	{
	public:
		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;
			while (child>0)
			{
				if (_com(_con[child] , _con[parent]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void adjust_down(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _com(_con[child + 1] ,_con[child]))
				{
					++child;
				}
				if (_com(_con[child], _con[parent]))
				{
					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;
		Compare _com;
	};
	void test_priority_queue()
	{
		priority_queue<int, vector<int>, greater<int>> pq;
		pq.push(4);
		pq.push(7);
		pq.push(2);
		pq.push(9);
		pq.push(3);
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}