#include <iostream>
#include <assert.h>
#include<stdlib.h>
#include <vector>
using namespace std;
template<typename T>
struct Big
{
	bool operator()(const T& l,const T& r)
	{
		return l>r;
	}
};
template<typename T>
struct Less
{
	bool operator()(const T& l,const T& r)
	{
		return l<r;
	}
};
template<class T,template<class> class Compare>
class Heap//二叉堆
{
 
public:
	Heap()
	{}
    void HeapSort(T* a,size_t size)
	{
		_a.reserve(size);
		for(size_t i=0;i<size;i++)
		{
			_a.push_back(a[i]);
		}
		for(int i=(_a.size()-2)/2;i>=0;--i)
		{
			Adjustdown(i);
		}
		print(_a,size);
	}
	void Adjustup(size_t child)
	{
		Compare<T> com;
		size_t parent =(child-1)/2;
		while(child>0)
		{
			if(com(_a[child],_a[parent]))
			{
				swap(_a[parent],_a[child]);
				child=parent;
				parent=(child-1)/2;
			}
			else
			{
				break;
			}
		}
	}
	void Adjustdown(size_t parent)
	{
 
		size_t child =parent*2+1;
		while(child<_a.size())
		{
			Compare<T> com;
		if(child+1<_a.size()&&com(_a[child+1],_a[child]))
		{
			++child;
		}
			if(com(_a[child],_a[parent]))
			{
			swap(_a[parent],_a[child]);
			parent=child;
			child=parent*2+1;
		}
		else
		{
			break;
		}
		}
	}
	bool Empty()
	{
		return _a.size()==0;
	}
	T& top()
	{
		assert(!_a.empty());
		return _a[0];
	}
	void Push(const T& x)
	{
	 _a.push_back(x);
	 size_t _size=_a.size();
	 Adjustup(_size-1);
	 print(_a,_size);
	}
	void Pop()
	{
		size_t _size=_a.size();
		assert(_size>0);
		swap(_a[0],_a[_size-1]);
		_a.pop_back();
		_size=_a.size();
		Adjustdown(0);
		print(_a,_size);
	}
   void print(vector<T> a,size_t size)
   {
 
	   for(int i=0;i<size;i++)
	   {
		   cout<<a[i]<<" ";
	   }
	   cout<<endl;
   }
private:
	vector<T> _a;
};
template <class T,template<class> class Compare=Big>
class PriorityQueue//优先级队列
{
public:
	void Push(const T& x)
	{
		hp.Push(x);
	}
	void Pop()
	{
		hp.Pop();
	}
	int Top()
	{
		return hp.top();
	}
protected:
	Heap<T,Compare> hp;
};
void test()
{
	int Tree[]={23,12,33,45,15,46,17,78,59};
	Heap<int,Big> h1; 
	h1.HeapSort(Tree,sizeof(Tree)/sizeof(Tree[0]));
}
void test2()
{
	int arr[] = { 12,10,43,23,22,67,9 };
	Heap<int,Big>   h1;
	h1.HeapSort(arr,sizeof(arr)/sizeof(arr[0])); 
	Heap<int,Less>  h2;
	h2.HeapSort(arr,sizeof(arr)/sizeof(arr[0])); 
}
void test3()
{
	
	PriorityQueue<int,Big> pq;
	pq.Push(1);
	pq.Push(23);
	pq.Push(33);
	pq.Push(46);
	pq.Push(15);
	pq.Push(43);
	pq.Push(27);
	pq.Push(81);
    pq.Push(19);
    pq.Push(10);
	pq.Push(11);
	cout<<pq.Top()<<endl;
}