/* bo11-1.c k路平衡歸并的函數(shù) */
 FILE *fp[k+1]; /* k+1個(gè)文件指針(fp[k]為大文件指針)，全局變量 */
 typedef int LoserTree[k]; /* 敗者樹是完全二叉樹且不含葉子，可采用順序存儲(chǔ)結(jié)構(gòu) */
 typedef RedType ExNode,External[k+1]; /* 外結(jié)點(diǎn),有改變 */
 External b; /* 全局變量 */
 #define MINKEY INT_MIN
 #define MAXKEY INT_MAX

 void input(int i,KeyType *a)
 { /* 從第i個(gè)文件(第i個(gè)歸并段)讀入該段當(dāng)前第1個(gè)記錄的關(guān)鍵字到外結(jié)點(diǎn) */
   fread(a,sizeof(KeyType),1,fp[i]);
 }

 void output(int i)
 { /* 將第i個(gè)文件(第i個(gè)歸并段)中當(dāng)前的記錄寫至輸出歸并段 */
   ExNode a;
   a.key=b[i].key; /* 當(dāng)前記錄的關(guān)鍵字已讀到b[i].key中 */
   fread(&a.otherinfo,sizeof(InfoType),1,fp[i]);
   fwrite(&a,sizeof(ExNode),1,fp[k]);
 }

 void Adjust(LoserTree ls,int s)
 { /* 沿從葉子結(jié)點(diǎn)b[s]到根結(jié)點(diǎn)ls[0]的路徑調(diào)整敗者樹。算法11.2 */
   int i,t;
   t=(s+k)/2; /* ls[t]是b[s]的雙親結(jié)點(diǎn) */
   while(t>0)
   {
     if(b[s].key>b[ls[t]].key)
     {
       i=s;
       s=ls[t]; /* s指示新的勝者 */
       ls[t]=i;
     }
     t=t/2;
   }
   ls[0]=s;
 }

 void CreateLoserTree(LoserTree ls)
 { /* 已知b[0]到b[k-1]為完全二叉樹ls的葉子結(jié)點(diǎn)，存有k個(gè)關(guān)鍵字，沿從葉子 */
   /* 到根的k條路徑將ls調(diào)整成為敗者樹。算法11.3 */
   int i;
   b[k].key=MINKEY;
   for(i=0;i<k;++i)
     ls[i]=k; /* 設(shè)置ls中“敗者”的初值 */
   for(i=k-1;i>=0;--i) /* 依次從b[k-1]，b[k-2]，…，b[0]出發(fā)調(diào)整敗者 */
     Adjust(ls,i);
 }

 void K_Merge(LoserTree ls,External b)
 { /* 利用敗者樹ls將編號(hào)從0到k-1的k個(gè)輸入歸并段中的記錄歸并到輸出歸并段。 */
   /* b[0]至b[k-1]為敗者樹上的k個(gè)葉子結(jié)點(diǎn)，分別存放k個(gè)輸入歸并段中當(dāng)前 */
   /* 記錄的關(guān)鍵字。算法11.1 */
   int i,q;
   for(i=0;i<k;++i) /* 分別從k個(gè)輸入歸并段讀人該段當(dāng)前第一個(gè)記錄的關(guān)鍵字到外結(jié)點(diǎn) */
     input(i,&b[i].key);
   CreateLoserTree(ls); /* 建敗者樹ls，選得最小關(guān)鍵字為b[ls[0]].key */
   while(b[ls[0]].key!=MAXKEY)
   {
     q=ls[0]; /* q指示當(dāng)前最小關(guān)鍵字所在歸并段 */
     output(q); /* 將編號(hào)為q的歸并段中當(dāng)前（關(guān)鍵字為b[q].key）的記錄寫至輸出歸并段 */
     input(q,&b[q].key); /* 從編號(hào)為q的輸入歸并段中讀人下一個(gè)記錄的關(guān)鍵字 */
     Adjust(ls,q); /* 調(diào)整敗者樹，選擇新的最小關(guān)鍵字 */
   }
   output(ls[0]); /* 將含最大關(guān)鍵字MAXKEY的記錄寫至輸出歸并段 */
 }