外排序(多路平衡归并的实现)

[c]代码库

typedef int LoserTree[k]; /*败者树是完全二叉树且不含叶子，可采用顺序存储结构*/
typedef struct
{
	KeyType key;
} ExNode,External[k]; /*外结点，只存放待归并记录的关键码*/
void K_Merge ( LoserTree *ls,External *b ) /*k-路归并处理程序*/
{ /*利用败者树ls 将编号从0 到k-1 的k 个输入归并段中的记录归并到输出归并段*/
	/*b[0]到b[k-1]为败者树上的k 个叶子结点，分别存放k 个输入归并段中当前记录的关键码*/
	for ( i=0; i<k; i++ ) input ( b[i].key ); /*分别从k 个输入归并段读入该段当前第一个记录的*/
	/*关键码到外结点*/
	CreateLoserTree ( ls ); /*建败者树ls，选得最小关键码为b[0].key*/
	while ( b[ls[0]].key!=MAXKEY )
	{
		q=ls[0]; /*q 指示当前最小关键码所在归并段*/
		output ( q ); /*将编号为q 的归并段中当前(关键码为b[q].key 的记录写至输出归并段)*/
		input ( b[q].key ); /*从编号为q 的输入归并段中读入下一个记录的关键码*/
		Adjust ( ls,q ); /*调整败者树，选择新的最小关键码*/
	}
	output ( ls[0] ); /*将含最大关键码MAXKEY 的记录写至输出归并段*/
}
void Adjust ( LoserTree *ls,int s ) /*选得最小关键码记录后，从叶到根调整败者树，选下一个最小关键码*/
{ /*沿从叶子结点b[s]到根结点ls[0]的路径调整败者树*/
	t= ( s+k ) /2; /*ls[t]是b[s]的双亲结点*/
	while ( t>0 )
	{
		if ( b[s].key>b[ls[t]].key ) s<-->ls[t]; /*s 指示新的胜者*/
		t=t/2;
	}
	ls[0]=s;
}
void CreateLoserTree ( LoserTree *ls ) /*建立败者树*/
{ /*已知b[0]到b[k-1]为完全二叉树ls 的叶子结点存有k 个关键码，沿从叶子到根的k 条路径*/
	/*将ls 调整为败者树*/
	b[k].key=MINKEY; /*设MINKEY 为关键码可能的最小值*/
	for ( i=0; i<k; i++ ) ls[i]=k; /*设置ls 中“败者”的初值*/
	for ( i=k-1; k>0; i-- ) Adjust ( ls,i ); /*依次从b[k-1],b[k-2],…,b[0]出发调整败者*/
}