#include<vector>
#include<iostream>
#include<assert.h>
using std::vector;
using std::swap;

namespace Mack
{
	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 Sequence  = vector<T>,class Compare = greater<T>>
	class priority_queue
	{
	public:

		void AdjustUP(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (comp(c[child] , c[parent]))
				{
					swap(c[child], c[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& val)
		{
			c.push_back(val);
			AdjustUP(size() - 1);
		}

		void AdjustDown(size_t parent)
		{
			size_t child = parent * 2 + 1;
			while (child < size())
			{
				while (child + 1 < size() && comp(c[child + 1] , c[child]))
				{
					child++;
				}
				if(comp(c[child] , c[parent]))
				{
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			assert(size() >0);
			swap(c[0], c[size() - 1]);
			c.pop_back();
			AdjustDown(0);
		}

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

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

		const T& top() const 
		{
			return c.front();
		}

	private:
		Sequence c;
		Compare comp;
	};

}