#include <iostream.h>
#include <iomanip.h>
void sift(int A[],int n,int m)    //輸出以A[m]為根節點的子樹為堆
{
	int j,t;
	t=A[m];j=2*(m+1)-1;
	while(j<=n)
	{
		if(j<n && A[j]<A[j+1])   //j指示t的左右子樹根節點中的大者
			j++;
		if(t<A[j])
		{
			A[m]=A[j];
			m=j;
			j=2*(m+1)-1;
		}
		else
			j=n+1;
	}
	A[m]=t;
}
void heapsort(int A[],int n)
{
	int i,k,temp;
	k=n/2;
	for(i=k-1;i>=0;i--)
		sift(A,n-1,i);
	for(i=n-1;i>=1;i--)
	{
		temp=A[0];A[0]=A[i];A[i]=temp;
		sift(A,i-1,0);
	}
}
void main()
{
	int A[10],n=10;
	cout<<"請輸入要求排序的無序序列(10個數據):";
	for(int i=0;i<n;i++)
		cin>>A[i];
	cout<<"堆排序"<<endl<<"排序前:";
	for(i=0;i<n;i++)
		cout<<setw(3)<<A[i];
	cout<<endl;
	heapsort(A,n);
	cout<<"排序后:";
	for(i=0;i<n;i++)
		cout<<setw(3)<<A[i];
	cout<<endl;
}