用败者树优化K路归并排序

时间:2022-02-09 21:05:28

  图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]

         用败者树优化K路归并排序

                        图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,用败者树优化K路归并排序} Runl:{ 05, 44,用败者树优化K路归并排序}Run2:{ 10, 12,用败者树优化K路归并排序}                                        Run3:{ 29, 32,用败者树优化K路归并排序} Run4:{ 15, 56,用败者树优化K路归并排序}                                   

     其中,用败者树优化K路归并排序是段结束标志。利用败者树进行5路平衡归并排序的过程如图9.19(a)所示。其中的叶结点k0~k是各归并段Run[0]~Run[4]在归并过程中的当前对象的排序码,各非叶结点ls1~ls4。记忆两个子女结点中(排序码)小的对象所在归并段号人。记忆最小对象所在归并段号。
  在ls0中记忆的是当前找到的最小对象所在归并段号i,根据该段号可取出这个对象,将它送人结果归并段,再取该归并段的下一个对象,将其排序码送人ki,然后从该叶结点到根结点,自下而上沿子女一双亲路径进行比较和调整,使下一个具次小排序码的对象所在的归并段号调整到冠军位置。将最小对象05送人结果归并段后,该归并段下一个对象的排序码44替补L来,送人k1。k1与其双亲人。中所记忆的上次的败者k2中的排序码进行比较,k1是败者,其归并段号1记人双亲 ls3,胜者 k2继续与更上一层双亲ls1中所记忆的败者k4进行排序码比较,k4仍是败者,胜者k2的归并段号进人冠军位置ls0

               用败者树优化K路归并排序 

                  用败者树优化K路归并排序 

                            图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 路平衡归并排序算法

void kwaymerge ( Element *r ) {
    r = new Element[k];        //创建对象数组 

int *key = new int[k+1];        //创建外结点数组   

int *loser = new int[k];        //创建败者树数组   

for ( int i = 0; i < k; i++ )   //传送参选关键码 

       { InputRecord ( r[i] );  key[i] = r[i].key; }

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;     

adjust ( key, loser, k, q );      //调整

}

Output end of run marker;   //输出段结束标志

delete [ ] r;  delete [ ] key;  delete [ ] loser;

 

}
自某叶结点key[q]到败者树根结点的调整算法

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增大时,相应需增加输入缓冲区个数。如果可供使用的内存空间不变,势必要减少每个输入缓冲区的容量,使内外存交换数据的次数增大。