/* algo10-9.c 堆排序 */
 #include<stdio.h>
 typedef int InfoType; /* 定義其它數據項的類型 */
 #include"c9.h"
 #include"c10-1.h"
 typedef SqList HeapType; /* 堆采用順序表存儲表示 */
 void HeapAdjust(HeapType *H,int s,int m) /* 算法10.10 */
 { /* 已知H.r[s..m]中記錄的關鍵字除H.r[s].key之外均滿足堆的定義，本函數 */
   /* 調整H.r[s]的關鍵字,使H.r[s..m]成為一個大頂堆(對其中記錄的關鍵字而言) */
   RedType rc;
   int j;
   rc=(*H).r[s];
   for(j=2*s;j<=m;j*=2)
   { /* 沿key較大的孩子結點向下篩選 */
     if(j<m&&LT((*H).r[j].key,(*H).r[j+1].key))
       ++j; /* j為key較大的記錄的下標 */
     if(!LT(rc.key,(*H).r[j].key))
       break; /* rc應插入在位置s上 */
     (*H).r[s]=(*H).r[j];
     s=j;
   }
   (*H).r[s]=rc; /* 插入 */
 }

 void HeapSort(HeapType *H)
 { /* 對順序表H進行堆排序。算法10.11 */
   RedType t;
   int i;
   for(i=(*H).length/2;i>0;--i) /* 把H.r[1..H.length]建成大頂堆 */
     HeapAdjust(H,i,(*H).length);
   for(i=(*H).length;i>1;--i)
   { /* 將堆頂記錄和當前未經排序子序列H.r[1..i]中最后一個記錄相互交換 */
     t=(*H).r[1];
     (*H).r[1]=(*H).r[i];
     (*H).r[i]=t;
     HeapAdjust(H,1,i-1); /* 將H.r[1..i-1]重新調整為大頂堆 */
   }
 }

 void print(HeapType H)
 {
   int i;
   for(i=1;i<=H.length;i++)
     printf("(%d,%d)",H.r[i].key,H.r[i].otherinfo);
   printf("\n");
 }

 #define N 8
 void main()
 {
   RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
   HeapType h;
   int i;
   for(i=0;i<N;i++)
     h.r[i+1]=d[i];
   h.length=N;
   printf("排序前:\n");
   print(h);
   HeapSort(&h);
   printf("排序后:\n");
   print(h);
 }