一．最优归并模式

    在前面已看到两个分别包含n个和m个记录的已分类文件可以在o(n+m)时间内归并在一起而得到一个分类文件。当要把两个以上的已分类文件归并在一起时，可以通过成对地

重复归并已分类的文件来完成。例如，假定x1，x2，x3，x4是要归并的文件，则可以首先把xl和x2归并成文件yl，然后将yl和x3归并成y2，最后将y2和x4归并，从而得到想要的分类文件；也可以先把x1和x2归并成y1，然后把x3和x4归并成y2，最后归并y1和y2而得到想要的分类文件。给出n个文件，则有许多种把这些文件成对地归并成一个单一分类文件的方法。不同的配对法要求不同的计算时间。现在所要论及的问题是确定一个把n个已分类文件归并在一起的最优方法(即需要最少比较的方法)。

    例`1 xl，x2和x3是各自有30个记录、20个记录和10个记录的三个已分类文件，归并xl和x2需要50次记录移动，再与x3归并则还要60次移动，其所需要的记录移动总量是110。如果首先归并x2和x3(需要30次移动)，然后归并x1(需要60次移动)，则所要作的记录移动总数仅为90。因此，第二个归并模式比第一个要快些。

    试图得到最优归并模式的贪心方法是容易表达的。由于归并一个具有n个记录的文件和一个具有m个记录的文件可能需要n+m次记录移动，因此对于量度标准的一种明显的选择是：每一步都归并尺寸最小的两个文件。例如，有五个文件(f1，…，f：)，它们的尺寸为(20，30，10，5，30)，由以上的贪心策略就会产生以下的归并模式：f4和f3归并成z1( ＝15)；归并zl和f2得到z2( ＝35)；把f2和f5归并成z3( ＝60)；归并z2和z3而得到答案z4。记录移动总量是205。可以证明这是给定问题实例的最优归并模式。

图1 表示一个归并模式的二元归并树文件的长度(即记录数)。

 

    像刚才所描述的归并模式称为二路归并模式(每一个归并步包含两个文件的归并)。二路归并模式可以用二元归并树来表示。图1显示了一棵表示上面五个文件所得到的最优归并模式的二元归并树。叶结点被画成方块形，表示这五个已知的文件。这些结点称为外部结点。剩下的结点被画成圆圈，称为内部结点。每个内部结点恰好有两个儿子，它表示把它的两个儿子所表示的文件归并而得到的文件。每个结点中的数字都是那个结点所表示的    外部结点f4在距离根结点z4为3的地方(一个i级结点在距离根为i一1的地方)，因此文件f4的记录都要移动三次，一次得到z1，一次得到z2，最后移动一次就得到z4。如果凡是由根到代表文件n的外部结点的距离，qi是fj的长度，则这棵二元归并树的记录移动总量是   

这个和数叫做这棵树的带权外部路径长度。   

一个最优二路归并模式与一棵具有最小权外路路径的二元树相对应，算法6的过程tree使用上面所叙述的规则去获得n个文件的二元归并树。，这算法把n个树的表l作为输入。树中的每一个结点有三个信息段，lchld，rchild和weight。起初，l中的每一棵树正好有一个结点。这个结点是一个外部结点，而且其lch丸d和rchild信息段为0·，而weight是要归并的n个文件之一的长度。在这个算法运行期间，对于l中的任何一棵具有根结点t的树，weight(t)表示要归并的文件的长度(weight(t)等于树t中外部结点的长度的和)。过程tree用了三个子算法，getnode(t)，least和insert(l，t)。子算法getnode(t)为构造这棵树提供一个新结点。least(l)找出l中一棵其根具有最小的weight 69树，并把这棵树从l中删去。insert(l，t)把根为丁的树插入到表l中。定理3．4将证明贪心过程tree(算法3．6)产生一棵最优的二元归并树。

算法6 生成二元归并树算法   

    line proceduretree (l，n)(动画)

／／l是如上所述的n个单结点二元树的表//

 for iß1 to n-1 do    

    call  getnode(t) ／／用于归并两棵树／／   

    lchild (t)<--least(l) ／／最小的长度／

    rchild (t)<--least(l)

    weight(t)<--weight(lchild(t))+weight(rchild(t))

    call insert(l，t)

repeat    return(least(l))

／／留在l中的树是归并树"

   end tree

   (动画演示)

 例2 当l最初表示其长度为2，3，5，7，9，13六个文件时，算法tree是如何工作的。图显示出在for循环的每一次迭代结束时的表l。在算法结束时所产生的二元归并树可以用来确定归并了哪些文件。归并是在这棵树中“最低”(有最大的深度)的那些文件上进行的。

    现在来分析算法6需要的计算时间。主循环执行n一1次。如果保持l按照这些根中的weight值的非降次序，则least(l)只需要o(1)时间，insert(l，t)在o(n)时间内被执行。因此所花费的时间总量是o(n’)。在l被表示成一个min—堆的情况下，其中根的值不超过它的儿子们的值，则least(l)和insert(l，t)可以在o(10gn)时间内完成(least(l)和insert(l，t)的算法以及其计算时间分析留作习题)。在这种情况下tree的计算时间是o(nlogn)。将第6行的insert和第4行的least结合起来还可以加快一些速度。   

 定理 若l最初包含n≥1个单个结点的树，这些树有weight值为(q1，q2，…，q9)，则算法tree对于具有这些长度的n个文件生成一棵最优的二元归并树，

  

 证明： 通过施归纳于n来证明。对于n＝1，返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于所有的(q1，q2 … qn)，1≤m<n，生成一棵最优二元归并树，现在来证明对于所有的(q1，q2 … qn)也生成最优的树。不失一般性，假定ql≤q2≤…≤qn，且ql和q2是在for循环的第一次迭代期间由第3行和第4行中的算法least所拽到的两棵树的weight信息段的值。于是就生成了图3．4的子树t。设t’是一棵对于(q1，q2，…，qn)的最优二元归并树。设P是距离根最远的一个内部结点。如果P的儿子不是q1和q2，则可以用q1和q2来代换P现在的儿子而不增加t’的带权外部路径长度。因此t也是一棵最优归并树中的子树。于是在t’中如果甩其权为q1+q2的一个外部结点来代换t，则所产生的树t’’是关于(q1+q2，q3，…，qn)的一棵最优归并树。由归纳假设，在用其权为ql+q2的那个外部结点代换了t以后，过程tree转化成去求取一棵关于(ql+q2，q3，…，qn)的最优归并树。因此tree生成一棵关于(q1，q2，…，qn)的最优归并树。证毕。

    生成归并树的贪心方法也适用于k路归并的情况。在这种情况下，相应的归并树是一棵k元树。由于所有的内部结点的度数必须为k，因此对于n的某些值，就不与k元归并树相对应。例如，当k＝3时，就不存在具有n＝2个外部结点的k元归并树。所以有必要引进一定量的“虚”外部结点.每一个虚结点被赋以0值的qi。这个虚值不会影响所产生的k元树的带权外部路径长度。本章习题11表明其所有内部结点都具有度数为k的k元树的存在性，只有当外部结点数n满足等式n mod(k一1)＝1时才成立。因此至多应增加k一2个虚结点。生成最优归并树的贪心规则是：在每一步，选取k棵具有最小长度的子树用于归并。关于它的最优性证明，则留作习题。