#include <iostream.h>
#include <stdlib.h>

template <class T> class MinHeap
{
	private:
		T *heapArray;
		int markArray;
		int MaxHeapSize;
		int heapSize;
		void FilterUp(int i);
		void FilterDown(int i);
	public:
		MinHeap(int maxSize);
		MinHeap(T arr[], int n);
		~MinHeap(void)
			{if(markArray == 0) delete heapArray;}

		void Insert(const T& item);
		T Delete(void);

		T GetHeaoTop()const
			{return heapArray[0];}
		int HeapSize(void)const
			{return heapSize;}
		int HeapEmpty(void)const
			{return heapSize == 0;}
		int HeapFull(void)const
			{return MaxHeapSize == heapSize;}
};

template <class T>
MinHeap<T>::MinHeap(int maxSize)
{
	if(maxSize <= 0 )
	{
		cerr << "參數maxSize非法! " << endl;
		exit(1);
	}
	MaxHeapSize = maxSize;
	heapSize = 0;
	heapArray = new T[maxSize];
	markArray = 0;
}

template <class T>
MinHeap<T>::MinHeap(T arr[], int n)
{
	if(n <= 0)
	{
		cerr << "參數n非法! " << endl;
		exit(1);
	}
	MaxHeapSize = n;
	heapSize = n;
	heapArray = arr;

	int currentPos = (n - 1) / 2;
	while(currentPos >= 0)
	{
		FilterDown(currentPos);
		currentPos--;
	}
	markArray = 1;
}

template <class T>
void MinHeap<T>::FilterUp(int i)
{
	int currentPos, parentPos;
	T target;

	currentPos = i;
	target = heapArray[i];
	parentPos = (i-1) / 2;
	while(currentPos != 0)
	{
		if(heapArray[parentPos] <= target) break;
		else
		{
			heapArray[currentPos] = heapArray[parentPos];
			currentPos = parentPos;
			parentPos = (currentPos - 1) / 2;
		}
	}
	heapArray[currentPos] = target;
}

template <class T>
void MinHeap<T>::Insert(const T& item)
{
	if(heapSize == MaxHeapSize)
	{
		cerr << "堆已滿! " << endl;
		exit(1);
	}
	heapArray[heapSize] = item;
	FilterUp(heapSize);
	heapSize++;
}

template <class T>
void MinHeap<T>::FilterDown(int i)
{
	int currentPos, childPos;
	T target;

	currentPos = i;
	target = heapArray[i];
	childPos = 2 * i + 1;
	while(childPos < heapSize)
	{
		if((childPos+1 < heapSize) && (heapArray[childPos+1] <= heapArray[childPos]))
			childPos = childPos + 1;

		if(target <= heapArray[childPos])
			break;
		else
		{
			heapArray[currentPos] = heapArray[childPos];
			currentPos = childPos;
			childPos = 2 * currentPos + 1;
		}
	}
	heapArray[currentPos] = target;
}

template <class T>
T MinHeap<T>::Delete(void)
{
	if(heapSize == 0)
	{
		cerr << "堆已空! " << endl;
		exit(1);
	}
	T item = heapArray[0];
	heapArray[0] = heapArray[heapSize-1];
	heapSize--;

	FilterDown(0);
	return item;
}