/* algo10-8.c 樹形選擇排序 */
 #include"c1.h"
 typedef int InfoType; /* 定義其它數(shù)據(jù)項的類型 */
 #include"c10-1.h"
 void TreeSort(SqList *L)
 { /* 樹形選擇排序 */
   int i,j,j1,k,k1,l,n=(*L).length;
   RedType *t;
   l=(int)ceil(log(n)/log(2))+1; /* 完全二叉樹的層數(shù) */
   k=(int)pow(2,l)-1; /* l層完全二叉樹的結(jié)點總數(shù) */
   k1=(int)pow(2,l-1)-1; /* l-1層完全二叉樹的結(jié)點總數(shù) */
   t=(RedType*)malloc(k*sizeof(RedType)); /* 二叉樹采用順序存儲結(jié)構(gòu) */
   for(i=1;i<=n;i++) /* 將L.r賦給葉子結(jié)點 */
     t[k1+i-1]=(*L).r[i];
   for(i=k1+n;i<k;i++) /* 給多余的葉子的關(guān)鍵字賦無窮大 */
     t[i].key=INT_MAX;
   j1=k1;
   j=k;
   while(j1)
   { /* 給非葉子結(jié)點賦值 */
     for(i=j1;i<j;i+=2)
       t[i].key<t[i+1].key?(t[(i+1)/2-1]=t[i]):(t[(i+1)/2-1]=t[i+1]);
     j=j1;
     j1=(j1-1)/2;
   }
   for(i=0;i<n;i++)
   {
     (*L).r[i+1]=t[0]; /* 將當(dāng)前最小值賦給L.r[i] */
     j1=0;
     for(j=1;j<l;j++) /* 沿樹根找結(jié)點t[0]在葉子中的序號j1 */
       t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
     t[j1].key=INT_MAX;
     while(j1)
     {
       j1=(j1+1)/2-1; /* 序號為j1的結(jié)點的雙親結(jié)點序號 */
       t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
     }
   }
   free(t);
 }

 void print(SqList L)
 {
   int i;
   for(i=1;i<=L.length;i++)
     printf("(%d,%d)",L.r[i].key,L.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}};
   SqList l;
   int i;
   for(i=0;i<N;i++)
     l.r[i+1]=d[i];
   l.length=N;
   printf("排序前:\n");
   print(l);
   TreeSort(&l);
   printf("排序后:\n");
   print(l);
 }