#include  "datastru.h"
#include  <stdio.h>

void sift(RECNODE *r, int i, int m)
{/*i是根結(jié)點(diǎn)編號,m是以i結(jié)點(diǎn)為根的子樹中最后一個(gè)結(jié)點(diǎn)的編號*/
	int j;
	RECNODE temp;

	temp = r[i];
	j = 2 * i;       /*j為i根結(jié)點(diǎn)的左孩子*/
	while(j <= m)
	  {if(j < m && (r[j].key < r[j + 1].key))
	    j++;                                  /*當(dāng)i結(jié)點(diǎn)有左右孩子時(shí),j取關(guān)鍵字大的孩子結(jié)點(diǎn)編號*/
	   if(temp.key < r[j].key)
	     { r[i] = r[j];   i = j;   j = 2 * i;}/*按堆定義調(diào)整,并向下一層篩選調(diào)整*/
	   else   break;                          /*篩選調(diào)整完成,跳出循環(huán)*/ 
	  }
	r[i] = temp;
}

void heapsort(RECNODE *r, int n)
{/*堆排序: n為r表中記錄數(shù),從r[1]開始放起*/
	int i;
	RECNODE temp;

	for(i = n/2; i >= 1; i--)
	  sift(r, i, n);             /*將無序序列建成大堆*/
	for(i = n; i >= 2; i--)
	  {temp = r[1];              /*堆頂及堆尾元素交換*/
	   r[1] = r[i];
	   r[i] = temp;
	   sift(r,1,i - 1);          /*交換后,從第一個(gè)元素開始調(diào)整為大堆,每次記錄個(gè)數(shù)少一個(gè)*/
	  }         
}

main( )
{ RECNODE  a[MAXSIZE];
  int  i, j, k, len;

 printf("\n\n輸入待排序數(shù)據(jù)(整數(shù)，以空格隔開，0 結(jié)束) : "); k = 0; scanf("%d",&j);
 while(j != 0) { k++; a[k].key = j; scanf("%d",&j); }
 len = k;
 printf("\n排序前 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i+1].key);
 printf("\n");
 heapsort (a,len);
 printf("\n\n排序后 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i+1].key);
 printf("\n\n");
}