#include<iostream.h>
#include<math.h>
#include<stdio.h>
#define MAXINT 32767
#define MAX 20
int sort(int *data,int n);/*錦標排序*/
int main()
{
	int data[MAX];
	int i,n;
	n=MAX;

	cout<<"input the numbers that you want to sort(<=20):"<<endl;
	cin>>n;
	if(n>20)
	{
		cout<<"Sorry! Please input a number again:"<<endl;
		cin>>n;
	}
	cout<<"please input "<<n<<" number to sort:"<<endl;
	for(i=0;i<n;i++)
	{
	   cin>>data[i];
	}
	sort(data,n);
	
	cout<<"\nSorted:"<<endl;
	for(i=0;i<n;i++)
	{
	   cout<<data[i]<<"  ";
	}
	cout<<endl;
	return 0;
}

int sort(int *data,int n)
{
   int *tree;
   int lChild,rChild,rt;
   int i,j,k,ii,exp;

   if(n<2)
	   return 1;
   /*計算數的層數*/
   exp=1;
   for(i=1;exp<n;i++)
   {
      exp=exp+exp;
   }
   k=i;

   /*計算數的結點*/
   exp=1;
   for(i=1;i<k;i++)
   {
	  exp=exp+exp;
   }
   exp=exp-1;
   exp=exp+n;

   //tree=malloc(exp*sizeof(int));
   tree=new int[exp];
   /*將待排序的關鍵字值移植到葉子節點上*/
   j=n-1;
   for(i=exp-1;i>=exp-n;i--)
   {
      tree[i]=data[j];
	  j--;
   }

   /*第一趟搜索最小葉子節點*/
   for(;i>-1;i--)
   {
      lChild=MAXINT;
	  rChild=MAXINT;
	  
	  ii=(i+1)+(i+1);
	  if(ii<=exp)
	  {
	     lChild=tree[ii-1];
	  }

	  if(ii+1<=exp)
	  {
	     rChild=tree[ii];
	  }

	  if(lChild<rChild)
	  {
	     tree[i]=lChild;
	  }
      else
	  {
	     tree[i]=rChild;
	  }
   }
   j=0;
   data[j]=tree[0];
   j++;
   /*第二趟及其后續各趟排序*/
   while(j<n)
   {
      /*設置選中的葉子結點值為MAXINT*/
	   rt=tree[0];
	   i=0;
	   do
	   {
	     ii=(i+1)+(i+1);
		 if(ii<=exp)
		 {
		    lChild=tree[ii-1];
			if(rt==lChild)
				i=ii-1;
		 }

		 if(ii+1<=exp)
		 {
		    rChild=tree[ii];
			if(rt==rChild)
				i=ii;
		 }

		 ii=(i+1)+(i+1);
		 /*確定葉子結點*/
		 if(ii>exp)
		 {
		    tree[i]=MAXINT;
			break;
		 }
	   }while(i+1<=exp);

	   /*查找本輪中最小的結點*/
	   while(i>0)
	   {
	      i=(i+1)/2;
		  i=i-1;
		  lChild=MAXINT;
		  rChild=MAXINT;

		  ii=(i+1)+(i+1);
		  if(ii<=exp)
		  {
		     lChild=tree[ii-1];
		  }

		  if(ii+1<=exp)
		  {
		     rChild=tree[ii];
		  }

		  if(lChild<rChild)
		  {
		     tree[i]=lChild;
		  }
		  else
		  {
		     tree[i]=rChild;
		  }
	   }
	   /*將選中的最小結點移到data數組中*/
	   data[j]=tree[0];
	   j++;
   }
   //free(tree);
   delete []tree;
   return 0;
}