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

 void input(int i,KeyType &a)
 { // 從第i個文件(第i個歸并段)讀入該段當前第1個記錄的關鍵字到外結點
   fread(&a,sizeof(KeyType),1,fp[i]);
 }

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

 void Adjust(LoserTree ls,int s)
 { // 沿從葉子結點b[s]到根結點ls[0]的路徑調整敗者樹。算法11.2
   int i,t;
   t=(s+k)/2; // ls[t]是b[s]的雙親結點
   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的葉子結點，存有k個關鍵字，沿從葉子
   // 到根的k條路徑將ls調整成為敗者樹。算法11.3
   int i;
   b[k].key=MINKEY;
   for(i=0;i<k;++i)
     ls[i]=k; // 設置ls中“敗者”的初值
   for(i=k-1;i>=0;--i) // 依次從b[k-1]，b[k-2]，…，b[0]出發調整敗者
     Adjust(ls,i);
 }

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