一．最優(yōu)歸并模式

    在前面已看到兩個分別包含n個和m個記錄的已分類文件可以在o(n+m)時間內(nèi)歸并在一起而得到一個分類文件。當(dāng)要把兩個以上的已分類文件歸并在一起時，可以通過成對地

重復(fù)歸并已分類的文件來完成。例如，假定x1，x2，x3，x4是要?dú)w并的文件，則可以首先把xl和x2歸并成文件yl，然后將yl和x3歸并成y2，最后將y2和x4歸并，從而得到想要的分類文件；也可以先把x1和x2歸并成y1，然后把x3和x4歸并成y2，最后歸并y1和y2而得到想要的分類文件。給出n個文件，則有許多種把這些文件成對地歸并成一個單一分類文件的方法。不同的配對法要求不同的計算時間。現(xiàn)在所要論及的問題是確定一個把n個已分類文件歸并在一起的最優(yōu)方法(即需要最少比較的方法)。

    例`1 xl，x2和x3是各自有30個記錄、20個記錄和10個記錄的三個已分類文件，歸并xl和x2需要50次記錄移動，再與x3歸并則還要60次移動，其所需要的記錄移動總量是110。如果首先歸并x2和x3(需要30次移動)，然后歸并x1(需要60次移動)，則所要作的記錄移動總數(shù)僅為90。因此，第二個歸并模式比第一個要快些。

    試圖得到最優(yōu)歸并模式的貪心方法是容易表達(dá)的。由于歸并一個具有n個記錄的文件和一個具有m個記錄的文件可能需要n+m次記錄移動，因此對于量度標(biāo)準(zhǔn)的一種明顯的選擇是：每一步都?xì)w并尺寸最小的兩個文件。例如，有五個文件(f1，…，f：)，它們的尺寸為(20，30，10，5，30)，由以上的貪心策略就會產(chǎn)生以下的歸并模式：f4和f3歸并成z1( ＝15)；歸并zl和f2得到z2( ＝35)；把f2和f5歸并成z3( ＝60)；歸并z2和z3而得到答案z4。記錄移動總量是205。可以證明這是給定問題實(shí)例的最優(yōu)歸并模式。

圖1 表示一個歸并模式的二元?dú)w并樹文件的長度(即記錄數(shù))。

 

    像剛才所描述的歸并模式稱為二路歸并模式(每一個歸并步包含兩個文件的歸并)。二路歸并模式可以用二元?dú)w并樹來表示。圖1顯示了一棵表示上面五個文件所得到的最優(yōu)歸并模式的二元?dú)w并樹。葉結(jié)點(diǎn)被畫成方塊形，表示這五個已知的文件。這些結(jié)點(diǎn)稱為外部結(jié)點(diǎn)。剩下的結(jié)點(diǎn)被畫成圓圈，稱為內(nèi)部結(jié)點(diǎn)。每個內(nèi)部結(jié)點(diǎn)恰好有兩個兒子，它表示把它的兩個兒子所表示的文件歸并而得到的文件。每個結(jié)點(diǎn)中的數(shù)字都是那個結(jié)點(diǎn)所表示的    外部結(jié)點(diǎn)f4在距離根結(jié)點(diǎn)z4為3的地方(一個i級結(jié)點(diǎn)在距離根為i一1的地方)，因此文件f4的記錄都要移動三次，一次得到z1，一次得到z2，最后移動一次就得到z4。如果凡是由根到代表文件n的外部結(jié)點(diǎn)的距離，qi是fj的長度，則這棵二元?dú)w并樹的記錄移動總量是   

這個和數(shù)叫做這棵樹的帶權(quán)外部路徑長度。   

一個最優(yōu)二路歸并模式與一棵具有最小權(quán)外路路徑的二元樹相對應(yīng)，算法6的過程tree使用上面所敘述的規(guī)則去獲得n個文件的二元?dú)w并樹。，這算法把n個樹的表l作為輸入。樹中的每一個結(jié)點(diǎn)有三個信息段，lchld，rchild和weight。起初，l中的每一棵樹正好有一個結(jié)點(diǎn)。這個結(jié)點(diǎn)是一個外部結(jié)點(diǎn)，而且其lch丸d和rchild信息段為0·，而weight是要?dú)w并的n個文件之一的長度。在這個算法運(yùn)行期間，對于l中的任何一棵具有根結(jié)點(diǎn)t的樹，weight(t)表示要?dú)w并的文件的長度(weight(t)等于樹t中外部結(jié)點(diǎn)的長度的和)。過程tree用了三個子算法，getnode(t)，least和insert(l，t)。子算法getnode(t)為構(gòu)造這棵樹提供一個新結(jié)點(diǎn)。least(l)找出l中一棵其根具有最小的weight 69樹，并把這棵樹從l中刪去。insert(l，t)把根為丁的樹插入到表l中。定理3．4將證明貪心過程tree(算法3．6)產(chǎn)生一棵最優(yōu)的二元?dú)w并樹。

算法6 生成二元?dú)w并樹算法   

    line proceduretree (l，n)(動畫)

／／l是如上所述的n個單結(jié)點(diǎ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 當(dāng)l最初表示其長度為2，3，5，7，9，13六個文件時，算法tree是如何工作的。圖顯示出在for循環(huán)的每一次迭代結(jié)束時的表l。在算法結(jié)束時所產(chǎn)生的二元?dú)w并樹可以用來確定歸并了哪些文件。歸并是在這棵樹中“最低”(有最大的深度)的那些文件上進(jìn)行的。

    現(xiàn)在來分析算法6需要的計算時間。主循環(huán)執(zhí)行n一1次。如果保持l按照這些根中的weight值的非降次序，則least(l)只需要o(1)時間，insert(l，t)在o(n)時間內(nèi)被執(zhí)行。因此所花費(fèi)的時間總量是o(n’)。在l被表示成一個min—堆的情況下，其中根的值不超過它的兒子們的值，則least(l)和insert(l，t)可以在o(10gn)時間內(nèi)完成(least(l)和insert(l，t)的算法以及其計算時間分析留作習(xí)題)。在這種情況下tree的計算時間是o(nlogn)。將第6行的insert和第4行的least結(jié)合起來還可以加快一些速度。   

 定理 若l最初包含n≥1個單個結(jié)點(diǎn)的樹，這些樹有weight值為(q1，q2，…，q9)，則算法tree對于具有這些長度的n個文件生成一棵最優(yōu)的二元?dú)w并樹，

  

 證明： 通過施歸納于n來證明。對于n＝1，返回一棵沒有內(nèi)部結(jié)點(diǎn)的樹且這棵樹顯然是最優(yōu)的。假定該算法對于所有的(q1，q2 … qn)，1≤m<n，生成一棵最優(yōu)二元?dú)w并樹，現(xiàn)在來證明對于所有的(q1，q2 … qn)也生成最優(yōu)的樹。不失一般性，假定ql≤q2≤…≤qn，且ql和q2是在for循環(huán)的第一次迭代期間由第3行和第4行中的算法least所拽到的兩棵樹的weight信息段的值。于是就生成了圖3．4的子樹t。設(shè)t’是一棵對于(q1，q2，…，qn)的最優(yōu)二元?dú)w并樹。設(shè)P是距離根最遠(yuǎn)的一個內(nèi)部結(jié)點(diǎn)。如果P的兒子不是q1和q2，則可以用q1和q2來代換P現(xiàn)在的兒子而不增加t’的帶權(quán)外部路徑長度。因此t也是一棵最優(yōu)歸并樹中的子樹。于是在t’中如果甩其權(quán)為q1+q2的一個外部結(jié)點(diǎn)來代換t，則所產(chǎn)生的樹t’’是關(guān)于(q1+q2，q3，…，qn)的一棵最優(yōu)歸并樹。由歸納假設(shè)，在用其權(quán)為ql+q2的那個外部結(jié)點(diǎn)代換了t以后，過程tree轉(zhuǎn)化成去求取一棵關(guān)于(ql+q2，q3，…，qn)的最優(yōu)歸并樹。因此tree生成一棵關(guān)于(q1，q2，…，qn)的最優(yōu)歸并樹。證畢。

    生成歸并樹的貪心方法也適用于k路歸并的情況。在這種情況下，相應(yīng)的歸并樹是一棵k元樹。由于所有的內(nèi)部結(jié)點(diǎn)的度數(shù)必須為k，因此對于n的某些值，就不與k元?dú)w并樹相對應(yīng)。例如，當(dāng)k＝3時，就不存在具有n＝2個外部結(jié)點(diǎn)的k元?dú)w并樹。所以有必要引進(jìn)一定量的“虛”外部結(jié)點(diǎn).每一個虛結(jié)點(diǎn)被賦以0值的qi。這個虛值不會影響所產(chǎn)生的k元樹的帶權(quán)外部路徑長度。本章習(xí)題11表明其所有內(nèi)部結(jié)點(diǎn)都具有度數(shù)為k的k元樹的存在性，只有當(dāng)外部結(jié)點(diǎn)數(shù)n滿足等式n mod(k一1)＝1時才成立。因此至多應(yīng)增加k一2個虛結(jié)點(diǎn)。生成最優(yōu)歸并樹的貪心規(guī)則是：在每一步，選取k棵具有最小長度的子樹用于歸并。關(guān)于它的最優(yōu)性證明，則留作習(xí)題。