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

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

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

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

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

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

 

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

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

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

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

    line proceduretree (l，n)(動(dòng)畫)

／／l是如上所述的n個(gè)單結(jié)點(diǎn)二元樹(shù)的表//

 for iß1 to n-1 do    

    call  getnode(t) ／／用于歸并兩棵樹(shù)／／   

    lchild (t)<--least(l) ／／最小的長(zhǎng)度／

    rchild (t)<--least(l)

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

    call insert(l，t)

repeat    return(least(l))

／／留在l中的樹(shù)是歸并樹(shù)"

   end tree

   (動(dòng)畫演示)

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

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

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

  

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

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