//堆排序
//要進行堆排序首先要創建堆，詳細算法思想見SelectSort.h
//算法實現
void CreatHeap(DataType a[],int n,int h)
//創建堆
{
	int i,j,flag;
	DataType temp;

	i=h;				//i為要創建堆的二叉樹根結點下標
	j=2*i+1;			//j為i的左孩子結點的下標
	temp=a[i];
	flag=0;
	//延左右孩子中值較大者重復向下篩選
	while(j<n&&flag!=1)
	{
		if(j<n-1&&a[j].key<a[j+1].key)	j++;
		
		if(temp.key>a[j].key)			//a[i].key>a[j].key
			flag=1;						//標記結束篩選條件
		else							//否則把a[j]上移
		{
			a[i]=a[j];
			i=j;
			j=2*i+1;
		}
	}
	a[i]=temp;							//把最初的a[i]賦予最后的a[j]

}


void InitCreatHeap(DataType a[],int n)		//初始化最大堆
{
	int i;
	for(i=(n-1)/2;i>=0;i--)
	{
		CreatHeap(a,n,i);
	}
}


void HeapSort(DataType a[],int n)
{
	int i;
	DataType temp;

	InitCreatHeap(a,n);			//init creat 最大堆

	for(i=n-1;i>0;i--)			//當前最大堆個數每次遞減1
	{
		
		//把頂堆a[0]元素和當前最大堆的最后一個元素交換
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;


		CreatHeap(a,i,0);		//調整根節點滿足最大堆
		
	}
}