#include <iostream.h>

template <typename type>
void swap( type &a, type &b)
{
	type temp;
	temp=a;
	a=b;
	b=temp;
}

template <typename type>
void shift_up( type a[], int i)
{
	bool done=false;
	if (i!=1)
	{
		while (!done && i!=1)
		{
			if (a[i]>a[i/2])
				swap(a[i],a[i/2]);
			else 
				done =true;
			i=i/2;
		}
	}
}

template <typename type>
void shift_down( type a[], int n, int i)
{
	bool done=false;
	if ((2*i)<=n)  {
		while (!done&&((i=2*i)<=n))  {

			if (i+1<=n && a[i+1]>a[i])
				i=i+1;
			if (a[i/2]<a[i])
				swap(a[i/2],a[i]);
			else  done=true;
		}
	}
}


template <typename type>
void insert(type a[], int &n, type x)
{
	n=n+1;
	a[n]=x;
	shift_up( a, n);
}

template <typename type>
void del(type a[], int &n, int i)
{
	type x,y;
	x=a[i];
	y=a[n];
	n=n-1;
	if (i<=n)
	{
		a[i]=y;
		if (y>=x)
		shift_up(a,i);
		else 
			shift_down(a,n,i);
	}
}

template <typename type>
type del_max( type a[], int &n)
{
	type x;
	x=a[1];
	del(a,n,1);
	return x;
}

template <typename type>
void make_heap1( type b[],type a[], int n)
{
	int i,m=0;
	for (i=0;i<n;i++)
		insert( a, m, b[i]);
}

template <typename type>
void make_heap2( type a[], int n)
{
	int i;
	for (i=n/2;i>=1;i--)  //從倒數第二層開始
		shift_down(a,n,i);
}

template <typename type>
void print_array(type a[], int n)
{
	for (int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}

template <typename type>
void heap_sort( type b[],type a[], int n)
{
	int i;
	make_heap1(b,a,n);
	for (i=n;i>1;i--){
		swap(a[1],a[i]);
	    shift_down(a,i-1,1);
	}
}

main()
{
	int b[12]={1,6,3,8,2,10,5,9,11,7,4};
	int a[12]={0};
//	make_heap1(b,a,11);
//	make_heap2(a,11);
	print_array(a,11);
	heap_sort(b,a,11);
	print_array(a,11);
}