計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第17章

PAGE7第17章平攤分析和斐波那契堆假設(shè)對(duì)某個(gè)數(shù)據(jù)結(jié)構(gòu)作n個(gè)操作。第i個(gè)操作實(shí)際需要的時(shí)間c(i)是：如果i正好是2的整數(shù)k次方，即i=2k，那么c(i)=i，否則c(i)=1。請(qǐng)用聚集法分析其平攤時(shí)間a(i)。解： 這n個(gè)操作總共需要的時(shí)間是：T(n)=i=1nc(i)=1≤i≤ni≠2k1+1≤i≤ni=n+k=1=n+(2lgn+1–2) n+2n3n。所以平攤時(shí)間是a(i)=T(n)/n3。用計(jì)賬法分析第1題中n次操作的時(shí)間復(fù)雜度。解： 第2種操作一次所需要的時(shí)間是，當(dāng)i=2k時(shí)，c(i)=i。我們注意到，在兩次第2種操作之間，從i=2k-1到i=2k(k2)第1種操作做了(2k-2k-1–1)=(2k-1–1)次。所以，如果我們給第1種操作多賦以2個(gè)單位時(shí)間并用來支付下一次的第2種操作，那么，第2種操作最多只需2個(gè)單位時(shí)間。很容易看到，這個(gè)觀察在k=0和k=1時(shí)，沒有第1種操作幫助，也正確。所以，為計(jì)算方便，我們可定義兩種操作的平攤時(shí)間如下：第1種操作的平攤時(shí)間是3，第2種操作的平攤時(shí)間也是3。那么，第2種操作的總時(shí)間2第1種操作的次數(shù)+2第2種操作的次數(shù)2第1種操作的次數(shù)+3第2種操作的次數(shù)所以，我們有如下分析：第1題中n次操作的總時(shí)間=第1種操作的總時(shí)間+第2種操作的總時(shí)間1第一種操作的次數(shù)+（2第1種操作的次數(shù)+3第2種操作的次數(shù)）=3第一種操作的次數(shù)+3第二種操作的次數(shù)=每次操作的平攤時(shí)間(第一種操作的次數(shù)+第二種操作的次數(shù))=3n=O(n)重新考慮例17.2中，有k位的二進(jìn)制計(jì)數(shù)器的連續(xù)增值問題。假設(shè)我們除了給二進(jìn)制計(jì)數(shù)器增值（即加1）的操作外，還允許在任意次連續(xù)增值后清零的操作，也就是把每個(gè)比特置為0的操作。另外，如果某次增值后的數(shù)字大于計(jì)數(shù)器能表達(dá)的范圍，也要清零。請(qǐng)解釋如何在二進(jìn)制計(jì)數(shù)器（即一個(gè)二進(jìn)制比特的序列）上實(shí)現(xiàn)增值（Increment）和清零（Reset）的操作，使得對(duì)初值為0的計(jì)數(shù)器進(jìn)行n次增值和清零的操作總共需要O(n)時(shí)間。請(qǐng)用計(jì)賬法分析這n個(gè)操作的復(fù)雜度。（提示：用一個(gè)指針指向最高位的1。）解： 我們用數(shù)組A[0..k-1]表示一個(gè)有k個(gè)比特的計(jì)數(shù)器。初始時(shí)，所有比特為0。另外，我們用一個(gè)指針maxA指向值為1的最高比特位。初始時(shí)，所有比特為0，置maxA=-1。下面是增值（Increment）和清零（Reset）的操作的偽碼。Increment(A)i0whilei<kandA[i]=1 A[i]0 ii+1endwhileifi<k then A[i]1 ifi>maxA //更新最高位的1的位置 thenmaxAi endif else maxA-1 //數(shù)字超出了計(jì)數(shù)器能表達(dá)的范圍endifEndReset(A) //清零fori0tomaxA A[i]0 //重置比特A[i] maxA-1 //更新指針maxAendforEnd在增值和清零的操作中，計(jì)入時(shí)間復(fù)雜度的基本操作及它們需要的實(shí)用時(shí)間可假設(shè)如下：把比特0翻轉(zhuǎn)為1需要一個(gè)單位時(shí)間把比特1翻轉(zhuǎn)為0需要一個(gè)單位時(shí)間重置一個(gè)比特需要一個(gè)單位時(shí)間更新指針maxA需要一個(gè)單位時(shí)間。我們?yōu)橐陨厦糠N基本操作設(shè)置平攤時(shí)間如下： 把0翻轉(zhuǎn)為1： 平攤時(shí)間=3(單位時(shí)間)把1翻轉(zhuǎn)為0： 平攤時(shí)間=0重置一個(gè)比特： 平攤時(shí)間=0更新指針maxA： 平攤時(shí)間=1。我們有以下分析：把0翻轉(zhuǎn)為1的基本操作的總次數(shù)：因?yàn)?翻轉(zhuǎn)為1只在增值操作中出現(xiàn)，且每次增值只需翻轉(zhuǎn)一次，所以有：把0翻轉(zhuǎn)為1的總次數(shù)增值操作的次數(shù)n。把1翻轉(zhuǎn)為0的基本操作的總次數(shù)：和書中例17.4的分析一樣，這個(gè)總次數(shù)把0翻轉(zhuǎn)為1的總次數(shù)。重置比特的總次數(shù)：重置比特的操作只出現(xiàn)在清零操作中。在一次清零操作中，重置比特的個(gè)數(shù)是p=maxA+1。因?yàn)橹羔榤axA能到達(dá)現(xiàn)在的位置，一定是從上一次清零開始，記數(shù)器中數(shù)經(jīng)過了p次進(jìn)位而得，也就是說，至少經(jīng)過了p次把比特0翻轉(zhuǎn)為1的操作。所以有： 重置比特的總次數(shù)把0翻轉(zhuǎn)為1的總次數(shù)。更新指針maxA的總次數(shù)：因?yàn)槊看卧鲋挡僮骰蚯辶悴僮髦校羔榤axA最多被更新一次，所以有：更新指針maxA的總次數(shù)增值操作的次數(shù)+清零操作的次數(shù)n。由上面的分析，我們得到對(duì)記數(shù)器進(jìn)行n次增值和清零操作的時(shí)間復(fù)雜度是：把0翻轉(zhuǎn)為1的總次數(shù)+把1翻轉(zhuǎn)為0的總次數(shù)+重置比特的總次數(shù)+更新maxA的總次數(shù)3把0翻轉(zhuǎn)為1的總次數(shù)+更新maxA的總次數(shù)=把0翻轉(zhuǎn)為1的平攤時(shí)間把0翻轉(zhuǎn)為1的次數(shù)+n3n+n=4n=O(n)。在第3章習(xí)題13中，我們介紹了最小優(yōu)先樹。對(duì)應(yīng)于數(shù)組A[1..n]的一個(gè)完全二叉樹T稱為最小優(yōu)先樹，如果它滿足以下條件：T的根存有數(shù)組A[1..n]中最小的數(shù)。假設(shè)根中的數(shù)為A[r]，則根的左子樹由數(shù)組A[1..r-1]中數(shù)遞歸建立，而根的右子樹由數(shù)組A[r+1..n]中數(shù)遞歸建立。當(dāng)數(shù)組為空時(shí)，對(duì)應(yīng)的子樹為葉結(jié)點(diǎn)而過程停止。顯然，在最小優(yōu)先樹中，父親結(jié)點(diǎn)里的數(shù)要小于等于兒子結(jié)點(diǎn)里的數(shù)。給定數(shù)組A[1..n]，下面的算法是用逐個(gè)插入的方法構(gòu)造其最小優(yōu)先樹。讓我們用T表示這棵樹。它有一個(gè)屬性T.root，指向這棵樹的根。樹中每個(gè)結(jié)點(diǎn)x可用子程序，MakeNode(x)，建立。它有4個(gè)屬性，其中x.key是存于這個(gè)結(jié)點(diǎn)的數(shù)字，x.left，x.right，x.parent是3個(gè)指針，分別指向左兒子，右兒子，和父親結(jié)點(diǎn)。屬性為空時(shí)，記為nil。建最小優(yōu)先樹的算法如下，Min-First(A[1..n],T) //n>1MakeNode(x) //建一結(jié)點(diǎn)x，它的4個(gè)屬性初始都是nilx.keyA[1] //把A[1]存入結(jié)點(diǎn)xT.rootx //x是樹根，樹中只插入一個(gè)數(shù)A[1]lastx //指針last指向最后插入到樹中的結(jié)點(diǎn)fori2ton //從A[2]開始，逐個(gè)插入這個(gè)二叉樹T MakeNode(new) new.keyA[i] //new.parent=new.left=new.right=nil whilelast.parentnilandlast.key>new.key lastlast.parent //沿last到根的路徑，找小于等于A[i]的數(shù) endwhile iflast.parent=nilandlast.key>new.key //last是根，表示A[i]小于樹里所有數(shù)字 then new.leftlast //原來的樹成了A[i](=new.key)的左兒子 last.parentnew //保持new.parent=new.right=nil T.rootnew //A[i]是新的樹根 else new.leftlast.right //否則last的右子樹成為A[i]的左子樹 last.rightnew //A[i]成為last的右子樹 new.parentlast //雙向聯(lián)結(jié) ifnew.leftnil //也就是原先的last.right thennew.left.parentnew //因?yàn)橐p向聯(lián)結(jié) endif endif lastnew //有l(wèi)ast.right=new.right=nilendforEnd證明算法Min-First的正確性。用平攤分析的計(jì)賬法證明算法Min-First的復(fù)雜度是O(n)。用平攤分析的勢能法證明算法Min-First的復(fù)雜度是O(n)。解： (a) 證明算法Min-First的正確性。我們歸納證明以下命題：插入第i個(gè)數(shù)后的二叉數(shù)是A[1..i]的一個(gè)最小優(yōu)先樹。歸納基礎(chǔ)：當(dāng)i=1時(shí)，算法一開始建立一個(gè)數(shù)A[1]的二叉數(shù)。這顯然是一個(gè)最小優(yōu)先樹。歸納步驟：假設(shè)插入A[i-1]后的樹T是A[1..i-1]的一個(gè)最小優(yōu)先樹(i2)。我們證明，插入A[i]后的樹也是一個(gè)最小優(yōu)先樹。因?yàn)锳[i-1]是序列A[1..i-1]最后一個(gè)數(shù)，last.key=A[i-1]，所以，樹T中對(duì)應(yīng)A[i-1]的結(jié)點(diǎn)的右子樹一定是空(nil)，而且它是樹中最右邊的一個(gè)葉子。如果我們順著從A[i-1]到根這條路徑走的話，數(shù)字會(huì)一個(gè)比一個(gè)小。當(dāng)我們碰到一個(gè)結(jié)點(diǎn)的數(shù)a滿足aA[i]時(shí)停下。假定結(jié)點(diǎn)a的右兒子是數(shù)字b，那么我們有aA[i]<b。這說明，未插入A[i]前，a嚴(yán)格小于序列A[1..i-1]中它右邊的任何數(shù)，而b是a右邊數(shù)中最小的。因?yàn)楝F(xiàn)在有aA[i]<b，那么，A[i]就是序列A[1..i]中點(diǎn)a右邊最小的數(shù)。所以，A[i]可成為a的右兒子。因?yàn)锳[i]是序列A[1..i]中最后的數(shù)，所以，序列A[1..i-1]中點(diǎn)a右邊的所有數(shù)形成A[i]的左子樹。顯然，這棵左子樹正好是未插入A[i]前，以b為根的子樹，也就是a的右子樹。因?yàn)锳[i]是序列A[1..i]中最后的數(shù)，它的右子樹必定是空(nil)。容易看出，如果b=nil，那么必有a=A[i-1]，算法仍然正確。所以，按以下步驟插入A[i]后的二叉樹仍然是最小優(yōu)先樹。順著從A[i-1](也就是結(jié)點(diǎn)last)到根的路徑找到第一個(gè)結(jié)點(diǎn)A[k]滿足A[k]A[i]。如果A[k]=nil和A[k]>A[i]，那么A[i]是所有數(shù)中最小的，它成為樹根。A[1..i-1]形成的最小優(yōu)先樹成為A[i]的左兒子。跳過步驟(3)(4)(5)。不論A[k]nil或者A[k]=nil，有A[k]A[i]。那么，A[i]是A[k]右邊最小的數(shù)，切下A[k]的右兒子R。置A[k]的右兒子為A[i]，并置A[i]的父親為A[k]。置A[i]的左兒子為R。如Rnil，置R的父親為A[i]。置A[i]的右兒子為一片樹葉。題中算法正是實(shí)現(xiàn)上面的步驟。所以歸納成功，算法正確。 (b)用平攤分析的計(jì)賬法證明算法Min-First的復(fù)雜度是O(n)?，F(xiàn)在來分析一下復(fù)雜度。算法Min-First每次插入一個(gè)數(shù)A[i]時(shí)做以下3件事。為這個(gè)數(shù)建一個(gè)結(jié)點(diǎn)，這只需常數(shù)時(shí)間，可認(rèn)為是一個(gè)單位時(shí)間。沿著A[i-1](=last)到根的路徑走，直到發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的數(shù)a滿足aA[i]時(shí)停下或發(fā)現(xiàn)A[i]比根還小時(shí)停下。這一步由第7行的while循環(huán)完成。把結(jié)點(diǎn)a的右子樹切下，取而代之，結(jié)點(diǎn)A[i]成為結(jié)點(diǎn)a的右子樹。這棵切下的子樹成為結(jié)點(diǎn)A[i]的左子樹，而A[i]的右子樹是一片樹葉。如果A[i]比根還小，那么結(jié)點(diǎn)A[i]成為樹根，而原樹根成為結(jié)點(diǎn)A[i]的左兒子。不論哪種情況，這第3件事只需常數(shù)時(shí)間，也可認(rèn)為是一個(gè)單位時(shí)間。上面第2件事所需時(shí)間與比較的次數(shù)成正比。我們注意到，除了最后比較的結(jié)點(diǎn)a外，其它任何與A[i]比較過的數(shù)字將不會(huì)再有比較。這是因?yàn)檫@些比較過的結(jié)點(diǎn)，除結(jié)點(diǎn)a外，屬於被切去的結(jié)點(diǎn)a的右子樹，而一旦被切去，這棵子樹中所有的點(diǎn)就不再有可能與以后插入的任何數(shù)比較了。因此，如果把一次比較的時(shí)間也算為一個(gè)單位時(shí)間，那么這第2件事所需時(shí)間等于1(A[i]與點(diǎn)a的比較)加上比較后被切去的結(jié)點(diǎn)數(shù)。因?yàn)槊總€(gè)結(jié)點(diǎn)最多只能被切去一次，所以導(dǎo)致結(jié)點(diǎn)被切去的比較次數(shù)總共不會(huì)大于n。當(dāng)然，這第2件事的最后一次比較，即與點(diǎn)a的比較，不導(dǎo)致結(jié)點(diǎn)a被切去。但是這樣的比較次數(shù)總共不會(huì)大于n。所以，這n次插入中第2件事所需要的總時(shí)間不大于n+n=2n。由以上分析，我們可各附加一個(gè)單位時(shí)間給第一件和第三件事，即它們的平攤時(shí)間都是2。因?yàn)閚次插入產(chǎn)生2n個(gè)附加的單位時(shí)間，足夠支付第二件事所需時(shí)間，我們可把第二件事所需平攤時(shí)間定為0。所以，n次插入的總時(shí)間最多是：平攤時(shí)間(第一件事次數(shù)+第二件事次數(shù))=22n=4n=O(n)。因此，算法Min-First的復(fù)雜度是O(n)。(c) 用平攤分析的勢能法證明算法Min-First的復(fù)雜度是O(n)。由問題(b)知，算法Min-First每次插入一個(gè)數(shù)時(shí)做3件事。一是為這個(gè)數(shù)建一個(gè)結(jié)點(diǎn)，需1個(gè)單位時(shí)間。二是沿著A[i-1]到根的路徑走，直到發(fā)現(xiàn)a滿足aA[i]或A[i]比根還小。第三件事是把結(jié)點(diǎn)a的右子樹切下，結(jié)點(diǎn)A[i]成為結(jié)點(diǎn)a的右子樹，這棵切下的子樹成為結(jié)點(diǎn)A[i]的左子樹，而A[i]的右子樹是一片樹葉。這第三件事也可認(rèn)為需要1個(gè)單位時(shí)間。這第二件事所需時(shí)間與比較的次數(shù)成正比。我們注意到，這第二件事所需時(shí)間等于1(與點(diǎn)a的比較)加上比較后被切去的結(jié)點(diǎn)數(shù)。因?yàn)槊總€(gè)結(jié)點(diǎn)最多只能被切去一次，所以導(dǎo)致結(jié)點(diǎn)被切去的比較次數(shù)不會(huì)大于n。 根據(jù)以上分析，我們定義一棵最小優(yōu)先樹的勢能函數(shù)：=從根到最右邊葉結(jié)點(diǎn)的路徑上的內(nèi)結(jié)點(diǎn)的個(gè)數(shù)–1。(也就是關(guān)鍵字的個(gè)數(shù)–1)。顯然，一開始，算法建立只含一個(gè)關(guān)鍵字的二叉樹，我們有(0)=1–1=0。又因?yàn)槊看尾迦胍粋€(gè)數(shù)后，這條路徑上至少有一個(gè)內(nèi)結(jié)點(diǎn)，所以(i)0。這個(gè)勢能函數(shù)的定義正確。我們注意到，插入第i個(gè)數(shù)A[i]需要的實(shí)際時(shí)間是2+k,其中k是第二件事所需比較的次數(shù)。勢能的增量最多是–k+2，這是因?yàn)橹辽儆衚-1個(gè)數(shù)字要從這個(gè)路徑上被切走，但是A[i]會(huì)加入到這個(gè)路徑上。所以，插入第i個(gè)數(shù)的平攤時(shí)間最多是2+k–k+2=4。因此，算法Min-First的復(fù)雜度是O(4n)=O(n)。在17.2.2一節(jié)，我們用如下一個(gè)例子證明用裝填因子0.5作為收縮的標(biāo)準(zhǔn)不行。假設(shè)當(dāng)前表格T的容量是size(T)=2k和number(T)=2k-1。如果下面兩個(gè)操作是插入，那么，在插入第一個(gè)數(shù)后，我們需要把表格擴(kuò)張后插入第2個(gè)數(shù)，總共用時(shí)2k+2個(gè)單位時(shí)間。如果接下來兩個(gè)操作是刪除，那么，因?yàn)閯h除兩個(gè)數(shù)據(jù)后的表格有number(T)=2k-1，導(dǎo)致小于0.5的裝填因子，我們需要在刪除第一個(gè)數(shù)后把表格收縮，總共用時(shí)也是2k+2個(gè)單位時(shí)間。這時(shí)，表格恢復(fù)到這4次操作前的狀態(tài)?？梢韵胂?，如果我們接下去有一系列的插入2個(gè)和刪除2個(gè)的操作，那么平均一次操作的時(shí)間是2k-1+1。因?yàn)閗不是常數(shù)，所以，用0.5的裝填因子作為表格收縮的標(biāo)準(zhǔn)不可能保證平均一次操作的時(shí)間是常數(shù)。以上的證明不是很嚴(yán)格，因?yàn)樯厦娴姆蠢皇菑目毡黹_始。另外，如果我們固定一個(gè)正整數(shù)k，然后給出一系列插入2個(gè)和刪除2個(gè)的操作，那么對(duì)一個(gè)給定的k，2k-1+1是常數(shù)。請(qǐng)嚴(yán)格證明，如果用裝填因子0.5作為收縮的標(biāo)準(zhǔn)，那么存在一個(gè)例子使得平均一次操作的時(shí)間可以任意大。解： 如果用裝填因子0.5作為收縮的標(biāo)準(zhǔn)，我們考慮下面的一系列對(duì)表格的插入和刪除操作。設(shè)開始時(shí)，k=1，size(T)=2=2k，number(T)=1=2k-1。取一正整數(shù)h>0。重復(fù)2k次插入2個(gè)數(shù)和刪除2個(gè)數(shù)的操作。這需要(2k+1+4)2k個(gè)單位時(shí)間。size(T)和number(T)不變。插入2k個(gè)數(shù)使size(T)=2k+1，number(T)=2k+1-1。這需要(2k+2k)=2k+1個(gè)單位時(shí)間(包括一次擴(kuò)展)。以上兩步，我們一共進(jìn)行了52k個(gè)插入和刪除操作，至少需要2k+12k>4k個(gè)單位時(shí)間?，F(xiàn)在，k變成k+1了。不斷重復(fù)上面(1)(2)兩步直到k=h+1。這樣，我們一共進(jìn)行了k=1h5×2k52h+1=102h個(gè)插入和刪除操作。因?yàn)橹辽傩枰偣瞜=1h4k4h個(gè)單位時(shí)間，所以平均一次操作的時(shí)間>4h/(10因?yàn)檎麛?shù)h可以取的任意大，所以存在一個(gè)例子使得平均一次操作的時(shí)間可以任意大。證明，對(duì)任一給定正整數(shù)n，都可以通過一系列的斐波那契堆的操作得到只含一棵樹的斐波那契堆。并且，這棵樹上有n個(gè)結(jié)點(diǎn)，它們形成一條鏈，即除最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)兒子，最后一個(gè)結(jié)點(diǎn)的兒子是nil。解： 給定正整數(shù)n，我們把這樣一顆樹稱為一個(gè)鏈條(chain)。我們先為n=1和n=2設(shè)計(jì)一個(gè)子程序如下。1-chain(H,x) //含一個(gè)點(diǎn)x的鏈條Make-Fib-Heap(H)createanobjectu //為x建一個(gè)結(jié)點(diǎn)的對(duì)象uu.keyxFib-Heap-Insert(H,u)End2-chain(H,a,b) //建含兩個(gè)點(diǎn)a和b，0<a<b，的鏈條1-chain(H,a)createanobjectv //為b建一個(gè)結(jié)點(diǎn)vv.keybFib-Heap-Insert(H,v)createanobjectw //為數(shù)字0建一個(gè)結(jié)點(diǎn)ww.key0Fib-Heap-Insert(H,w)Fib-Heap-Extract-Min(H)End1-chain的正確性顯然。2-chain的正確性也顯然。在建立一個(gè)點(diǎn)a的斐波那契堆后，我們插入b和0。這時(shí)，樹根環(huán)有3棵樹，分別含有關(guān)鍵字0，a，b。因?yàn)?<a<b，當(dāng)我們刪除最小點(diǎn)時(shí)，含0的樹被刪去，而點(diǎn)a和點(diǎn)b則合并為一棵以a為根的樹。它有唯一的兒子b。這棵樹就是一個(gè)2-chain。當(dāng)n>2時(shí)，我們?yōu)镃hain設(shè)計(jì)以下遞歸算法。Chain(H,A[p..r],n) //設(shè)0<A[p]<A[p+1]<…<A[r],r-p+1=nifn=1 then 1-chain(H,A[p]) returnendififn=2 then 2-chain(H,A[p],A[p+1]) return else Chain(H1,A[p+1...r],n-1) //遞歸調(diào)用 yA[r]+1 2-chain(H2,A[p],y) //A[p]最小，y最大 Fib-Heap-Union(H,H1,H2) createanobjectw w.key0 Fib-Heap-Insert(H,w) Fib-Heap-Extract-Min(H) Fib-Heap-Delete(H,y)End上面?zhèn)未a的正確性可以歸納證明。當(dāng)n=1和2時(shí)，偽碼顯然正確。假設(shè)當(dāng)n=1,2,…,k時(shí)，偽碼可以正確地建立只含一棵樹的斐波那契堆。并且，堆中k個(gè)結(jié)點(diǎn)形成一條鏈。我們證明，當(dāng)n=k+1時(shí)，偽碼仍正確。由偽碼第8行知，當(dāng)n=k+1時(shí)，偽碼先遞歸地建立只含一棵樹的斐波那契堆H1，堆中k個(gè)結(jié)點(diǎn)形成一條鏈，樹根是A[p+1]。然后，算法產(chǎn)生只含兩個(gè)數(shù)，A[p]和y=A[r]+1的的斐波那契堆H2。當(dāng)我們合并H1和H2為H后，堆H有兩個(gè)樹根，A[p]和A[p+1]。插入點(diǎn)w=0后有3個(gè)樹根。所以，偽碼第14行刪除最小點(diǎn)后，子程序Consolidate(H)會(huì)把根A[p+1]聯(lián)到A[p]上，從而得到一棵樹的斐波那契堆H。顯然，把點(diǎn)y從點(diǎn)A[p]上切除后，這棵樹是一個(gè)從A[p]到A[r]的一條鏈。歸納成功。假設(shè)有一個(gè)斐波那契堆如下圖所示，請(qǐng)比照?qǐng)D17-4，顯示刪除最小點(diǎn)的步驟和最后的斐波那契堆。1111H.min1735242810271320314219201422解： 刪除最小點(diǎn)的第一步是把最小點(diǎn)10的所有兒子并入樹根表，第二步把最小點(diǎn)10從樹根表中摘除。同時(shí)，指向最小點(diǎn)的指針指向最小點(diǎn)10右邊的點(diǎn)19。第三步做Cons