lost_k_merge.cpp

来自「常用算法与数据结构原代码」· C++ 代码 · 共 41 行

#define N 32
#define MIN_KEY -1
#define MAX_KEY 9999

void Adjust(int lost[],int s[],int sp,int k)
{
	int t,temp;
	t=(sp+k)/2;
	while (t>0)
	{
		if (s[sp]>s[lost[t]])
		{
			temp=sp;
			sp=lost[t];
			lost[t]=temp;
		}
		t/=2;
	}
	lost[0]=sp;
}

int K_Merge(int k)
{
	int lost[N],s[N+1];
	int i,t;
	for (i=0;i<k;i++)
		s[i]=get_next(i);
	s[k]=MIN_KEY;
	for (i=0;i<k;i++)
		lost[i]=k;
	for (i=k-1;i>=0;i--)
		Adjust(lost,s,i,k);
	while (s[lost[0]]!=MAX_KEY)
	{
		t=lost[0];
		put_record(&s[t]);
		s[t]=get_next(t);
		Adjust(lost,s,t,k);
	}
}