一．最優歸并模式

    在前面已看到兩個分別包含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棵具有最小長度的子樹用于歸并。關于它的最優性證明，則留作習題。