#include <iostream.h>
#include <math.h>
void main()
{int number;
 cout<<"請輸入要排序的數組元素的個數:";
 cin>>number;
 int *data=new int[number+1];           //運用數組指針
 void input(int *,int );                //輸入函數聲明
 void optimalheapsort(int *,int );      //堆排序的改進函數聲明
 void output(int *,int );               //輸出函數聲明
 input(data,number);
 optimalheapsort(data,number);
 output(data,number);
 delete data;                           //回收數組指針
}


void input(int *A,int n)                 //輸入函數定義
{cout<<"請輸入這"<<n<<"個元素:"<<endl;
 for (int i=1;i<=n;i++)
 	 cin>>A[i];
 cout<<endl;   
}


void optimalheapsort(int *A,int n)        //堆排序改進過程
{
 void buildheap(int *,int);
 void heapfify(int *,int,int,int);
 void rebuildheap(int *,int,int,int,int);
 buildheap(A,n);                           //調用建堆過程
 for (int j=n;j>=3;j--)
 {int temp=A[1];             
  int h=int (log(j-1)/log(2));             //h為樹高，強制轉化為整型
  int i=1;
  rebuildheap(A,n,i,(j-1),h);
  A[j]=temp;
 }
 int t=A[1];
 A[1]=A[2];
 A[2]=t;
}


void heapfify(int *B,int m,int x,int y)     //將數組B[x]-B[y]建成堆
{if ((2*x+1<=m) && ((B[2*x]>B[x]) || (B[2*x+1]>B[x])))
                                 //兩個兒子有比自身大時取其大者
{int k=2*x;
 if (B[2*x+1]>B[2*x])  
	 k=2*x+1;
 int t=B[x];
 B[x]=B[k];
 B[k]=t;
 heapfify(B,m,k,y);
}
else if ((2*x==m) && (B[2*x]>B[x])) 
                                //只有一個兒子且比自身大時取其兒子
{int k=2*x;
 int t=B[x];
 B[x]=B[k];
 B[k]=t;
 heapfify(B,m,k,y);
}
return;
}


void buildheap(int *B,int m)                 //將數組B[1]-B[m]建成堆
{for (int i=m/2;i>=1;i--)
      heapfify(B,m,i,m);
}


void rebuildheap(int *B,int m,int x,int y,int h1)  
                                             //重整數組B[x]-B[y]為堆
{
	if (h1==1)   {B[x]=B[y+1];               //當高度為1時整堆
              heapfify(B,y,x,y);}
else  {int count=1;
       while (count++<=h1/2)                 //左右兒子作一次比較，
		        //大者上升一層的過程只進行到當前堆的第h/2層的某結點處
	   {int k=2*x;
	    if (B[2*x+1]>B[2*x])
			k=2*x+1;
		B[x]=B[k];
		x=k;
	   }
	   if (B[y+1]>=B[x/2])     //B[y+1]在當前子堆中上升到某一合理位置
	   {B[x]=B[y+1];
	    while (B[x]>B[x/2]) 
		{int t=B[x];
		 B[x]=B[x/2];
		 B[x/2]=t;
		 x=x/2;
		}
	   }
	   else                     //遞歸地重新堆化當前子堆
	   {h1=h1-h1/2;
	    rebuildheap(B,m,x,y,h1);
	   }
}
}


void output(int *A,int n)         //輸出函數定義
{cout<<"排完序后的數組為:"<<endl;
 for (int i=1;i<=n;i++)
	 cout<<A[i]<<",";
 cout<<endl;
}