/*
	        用敗者樹進行外排序
			author:FangYuhao
			date:2008/10/25
            describtion:
			先用內(nèi)排序對隨即產(chǎn)生的內(nèi)n個3位數(shù)的整數(shù)排好序，存放在一個文件中，
			共產(chǎn)生m個有序文件，然后對這m個文件利用敗者樹進行多路平衡歸并，
			得到一個有n*m個三位數(shù)的有序文件。
 */
#include	<iostream>
#include	<algorithm>
#include    <ctime>
using		namespace    std;
#define		N 121
#define		M 5
FILE		*fp[M+1];
char		*name[6] = {"f0.dat","f1.dat","f2.dat","f3.dat","f4.dat","f5.dat"};
int         ls[M] , b[M + 1] ;
void		creatfile()
{
			int   a[N] , i , j ,seed , temp , n;
			srand(time(NULL));
			for(j = 0 ; j < M  ; j++)
			{
			       for(i = 1 ; i < N ; i++) a[i] = rand()%1000;
				   sort(a+1 ,  a+N);
				   fp[j] = fopen(name[j],"wb");
				   temp = 10000;
				   for(i = 1 ; i < N ; i++)
					    fwrite(&a[i],sizeof(int),1,fp[j]);
				   fwrite(&temp,sizeof(int),1,fp[j]); //寫入結束標志，這里用10000表示
				   fclose(fp[j]);
			}
}
void		adjust(int ls[] , int b[] , int s ,int k) // 敗者樹調(diào)整函數(shù)
{
			int t , temp;
			t = (s + k)  / 2;
			while(t)
			{
			        if (b[s] > b[ls[t]])
					{ 
						temp = s ;
						s = ls[t];
						ls[t] = temp;
					}
					t /= 2;
			}
			ls[0] = s;
}
void        crttree(int ls[] , int b[] , int k) // 建立敗者樹
{
            int  i ;
			b[k] = -100;
			for(i = 0 ; i <= k ; i++) ls[i] = k;
			for(i = k-1 ; i >= 0 ; i--)
				   adjust(ls,b,i,k);

}
void		kpathmerge(int ls[] , int b[] , int k) //k路平衡歸并
{
			int i ,  q;
			for(i = 0 ; i < k ; i++) fp[i] = fopen(name[i],"rb");
			fp[k] = fopen(name[k],"wb");
			for(i = 0 ; i < k ; i++)
				 fread(&b[i],sizeof(int),1,fp[i]);
			crttree(ls,b,k);
			while(b[ls[0]] != 10000)
			{
			         q = ls[0];
					 fwrite(&b[q] ,  sizeof(int) , 1 , fp[k]);
					 fread(&b[q] , sizeof(int) , 1 , fp[q]);
					 adjust(ls,b,q,k);
			}
			for(i = 0 ; i <= k ; i++) fclose(fp[i]);
}
int			main()
{
            int  n , temp , ans;
			creatfile();
			kpathmerge(ls,b,M);
			n = 0;
			fp[5] = fopen(name[5],"rb");
			while(!feof(fp[5]))        //輸出結果到屏幕
			{
			        fread(&temp , sizeof(int) , 1 , fp[5]);
					printf("%6d",temp);
					n++;
					if(n %10 == 0) printf("\n");
			}
			fclose(fp[5]);
			return 0;
}