图9.16给出的归并过程属于2路平衡归并。做K路平衡归并(k-way balanced merging)时,如果有m个初始归并段,则相应的归并树有[logkm]+1层,南非要归并[logkm]趟。
做内部归并时,在k个对象中选择最小者,需要顺序比较k-1次。每趟归并u个对象需要做(u-1)*(k-1)次比较,S趟归并总共需要的比较次数为:
S*(u-1)*(k-1)=[logkm]*(u-1)*(k-1)
=[log2m]*(u-1)*(k-1)/[log2k]
图9.18 对36个初始归并段做6路归并过程
其中的[log2m]*(u-1)在初始归并段个数 m与对象个数 u一定时是常数,而(k-1)/[log2k]在k增大时趋于无穷大。因此,增大归并路数k,会使得内部归并的时间 增大。
下面介绍一种使用“败者树”从h个归并段中选最小者的方法。对于较大的k(k≥ 6),可大大减少查找下一个排序码最小的对象时的比较次数。
利用败者树,在k个对象中选择最小者,只需要O([log2k])次排序码比较,这时有:
S*(u-1)*[log2k]=[logkm]*(u-1)*[log2k]
=[log2m]*(u-1)*[log2k]/[log2k]=[log2m]*(u-1)
这样,排序码比较次数与k无关,总的内部归并时间不会随k的增大而增大。因此, 只要内存空间允许,增大归并路数k,将有效地减少归并树高度,从而减少读写磁盘次数 d,提高外排序的速度。
败者树实际上是一棵完全二叉树。其中每个叶结点存放各归并段在归并过程中当前 参加比较的对象,每个非叶结点记忆它两个子女结点中对象排序码小的结点(即败者)。 因此,根结点中记忆树中当前对象排序码最小的结点。为叙述简单起见,以后把排序码最 小的对象称为最小对象。设有5个初始归并段,它们中各对象的排序码分别是:
Runo:{ 17, 21,} Runl:{ 05, 44,}Run2:{ 10, 12,} Run3:{ 29, 32,} Run4:{ 15, 56,}
其中,是段结束标志。利用败者树进行5路平衡归并排序的过程如图9.19(a)所示。其中的叶结点k0~k4是各归并段Run[0]~Run[4]在归并过程中的当前对象的排序码,各非叶结点ls1~ls4。记忆两个子女结点中(排序码)小的对象所在归并段号人。记忆最小对象所在归并段号。
在ls0中记忆的是当前找到的最小对象所在归并段号i,根据该段号可取出这个对象,将它送人结果归并段,再取该归并段的下一个对象,将其排序码送人ki,然后从该叶结点到根结点,自下而上沿子女一双亲路径进行比较和调整,使下一个具次小排序码的对象所在的归并段号调整到冠军位置。将最小对象05送人结果归并段后,该归并段下一个对象的排序码44替补L来,送人k1。k1与其双亲人。中所记忆的上次的败者k2中的排序码进行比较,k1是败者,其归并段号1记人双亲 ls3,胜者 k2继续与更上一层双亲ls1中所记忆的败者k4进行排序码比较,k4仍是败者,胜者k2的归并段号进人冠军位置ls0。
图9.19 利用败者树选最小对象
败者树高度为[log2k],在每次调整,找下一个具有最小排序码对象时,最多做 [log2k] 次排序码比较。
在实现利用败者树进行多路平衡归井算法时,把败者树的叶结点和非叫结点分开定 义。败者树的叶结点 key[k]有k+l个,key[0]~ key[k-1」存放各归并段当前参加归并 的对象的排序码,key[k]是辅助工作单元,在初始建立败者树时使用,存放一个最小的在各归并段中不可能出现的排序码:-MaxNum。败者树的非叶结点loser「k-l]有k个. 其中loser[l]~loser[k一1]川存放各次比较的败者的归并段号,loser[0」中是最后胜者所在 的归并段号。另外还有一个对象数组r[k],存放各归并段当前参加归井的对象。 在内存中应为每一个归并段分配一个输人缓冲区,其大小应能容纳一个页块的对象, 编号与归并段号一致。每个输人缓冲区应有一个指针,指示当前参加归并的对象。
初始时指向缓冲区第一个对象。每当一个对象i被选出并送人输出缓冲区后,InputRecord(i) 操作修改该对象所在输入缓冲区的指针,指向下一个参加归井的对象,并将这个对象读人 r[i〕,其排序码送人 key[i」。当该缓冲区指针指到块尾,表明缓冲区中对象已处理完,此时应从相应归并段读人下一个页块,并将缓冲区指针指到第一个对象。
在内存中还应设立一个输出缓冲区,其大小相当于一个页块大小。它也有一个缓冲 区指针,指示当前可存放结果对象的位置,初始时指向缓冲区第一个对象位置。每当一个对象i被选出,就执行OutputRecord(i)操作,将对象接输出缓冲区指针所指位置存放到输出缓冲区中,然后修改缓冲区指针,指到下一个存放位置。当输出缓冲区指针指到块尾,表明缓冲区已满,应将缓冲区中全部对象输出到结果归并段,再将缓冲区指针指到第一个对象位置。
k 路平衡归并排序算法
int *key = new int[k+1]; //创建外结点数组
int *loser = new int[k]; //创建败者树数组
for ( int i = 0; i < k; i++ ) //传送参选关键码
for ( i = 0; i < k; i++) loser[i] = k;
key[k] = -MaxNum; //初始化
for ( i = k-1; i; i-- ) //调整形成败者树
adjust ( key, loser, k, i );
while ( key[loser[0]] != MaxNum ) { //选归并段
q = loser[0]; //最小对象的段号
OutputRecord ( r[q] ); //输出
InputRecord ( r[q] ); //从该段补入对象
key[q] = r[q].key;
}
Output end of run marker; //输出段结束标志
delete [ ] r; delete [ ] key; delete [ ] loser;
void adjust ( int key[ ]; int loser[ ]; const int k;const int q ) {
//q指示败者树的某外结点key[q], 从该结点起到根
//结点进行比较, 将最小 key 对象所在归并段的段
//号记入loser[0]。k是外结点key[0..k-1]的个数。
for ( int t = (k+q) / 2; t > 0; t /= 2 ) // t是q的双亲
if ( key[loser[t]] < key[q]) //败者记入loser[t], 胜者记入q
{int temp = q; q = loser[t]; loser[t] = temp; } //q与loser[t]交换
loser[0] = q;
}
归并路数 k 的选择不是越大越好。归并路数 k增大时,相应需增加输入缓冲区个数。如果可供使用的内存空间不变,势必要减少每个输入缓冲区的容量,使内外存交换数据的次数增大。