計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第17章 平攤分析和斐波那契堆

1第17

章

平攤分析和斐波那契堆概述

2平攤分析的常用方法

5動(dòng)態(tài)表格

18只允許擴(kuò)張的動(dòng)態(tài)表格

20擴(kuò)張和收縮都有的動(dòng)態(tài)表格

26斐波那契堆

35可合并堆的操作

40減小關(guān)鍵字和刪除任一結(jié)點(diǎn)的操作

5721.概述斐波那契堆（Fibonacciheap）克服了二叉堆的缺點(diǎn)，使MST和Dijkstra算法有復(fù)雜度O(nlgn+m)。主要思路是，更新堆中數(shù)據(jù)后，不要馬上修復(fù)堆，而是打上個(gè)記號(hào)。這使得每次更新只需O(1)的時(shí)間。(實(shí)際操作是切下這點(diǎn)為根的子樹，插入到一個(gè)環(huán)中。)等到需要把最小值(或最大值)從堆中刪除時(shí)，再把需要修復(fù)的地方一次性全部修復(fù)，并保證不論有多少地方要修復(fù)，只要O(lgn)的時(shí)間。這里，n是堆中元素的個(gè)數(shù)。傳統(tǒng)的二叉堆用的是二叉樹，很難支持上述作法，斐波那契堆允許一個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)兒子，但不超過(guò)O(lgn)個(gè)。斐波那契堆的構(gòu)造和操作比較復(fù)雜。當(dāng)問題規(guī)模小時(shí)，人們還是用二叉堆。但規(guī)模大時(shí)，斐波那契堆的優(yōu)勢(shì)會(huì)在應(yīng)用中顯現(xiàn)出來(lái)。3平攤分析（amortizedanalysis）需要用平攤分析來(lái)證明斐波那契堆的復(fù)雜度，而平攤分析本身是一種分析算法復(fù)雜度的重要方法，我們先介紹平攤分析。平攤分析簡(jiǎn)介：算法往往需要對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)作一系列操作，它們使數(shù)據(jù)結(jié)構(gòu)的大小隨之動(dòng)態(tài)地變化。所以，每一次操作所需要的時(shí)間，會(huì)因?yàn)閿?shù)據(jù)結(jié)構(gòu)大小不同，會(huì)非常不同。為簡(jiǎn)化分析，通常用最壞情況時(shí)一次操作所需時(shí)間來(lái)估計(jì)。例如，修復(fù)一個(gè)堆有時(shí)不需要2lgn次比較，但我們都算作2lgn次比較。這樣的簡(jiǎn)化估計(jì)有時(shí)可得到足夠好的復(fù)雜度，例如堆排序。但是，很多時(shí)候這個(gè)簡(jiǎn)化的估計(jì)會(huì)導(dǎo)致很差的結(jié)果。對(duì)n次操作所需要的時(shí)間作精確分析往往較難。平攤分析的思路是，對(duì)一次操作平均需要的時(shí)間做一個(gè)估計(jì)。4平攤分析簡(jiǎn)介（繼續(xù)）要得到精確的平均值同樣難，所以，平攤分析的思路是：對(duì)一個(gè)操作平均需要的時(shí)間的上界做一個(gè)估計(jì)，使得一個(gè)操作實(shí)際需要的時(shí)間的平均值，在最壞情況下，不會(huì)超過(guò)我們估計(jì)的上界，但兩者又很接近，只差一個(gè)常數(shù)因子。顯然，這樣的估計(jì)會(huì)足夠好，因?yàn)樗删_地給出，最壞情況下，這n個(gè)操作的時(shí)間復(fù)雜度的階。

平攤分析就是研究如何能簡(jiǎn)單容易地得到這個(gè)上界的估計(jì)。注評(píng)：平攤分析得到的值不是算法平均情況的復(fù)雜度。算法平均情況的復(fù)雜度是考慮，算法被多次運(yùn)算時(shí)，平均一次算法的運(yùn)算所需要的時(shí)間。平攤分析只考慮算法運(yùn)算一次，但數(shù)據(jù)結(jié)構(gòu)被多次操作。它得到的是一次數(shù)據(jù)結(jié)構(gòu)的操作所需的平均時(shí)間。52.平攤分析的常用方法平攤分析的常用方法有聚集法，記賬法，和勢(shì)能法。聚集法(aggregateanalysis)簡(jiǎn)單地說(shuō)，聚集法就是一個(gè)算總帳的方法。例17.1 堆棧操作堆棧S通常提供兩種操作，并且每個(gè)操作只需O(1)時(shí)間:Push(S,x) //把元素x壓入堆棧S，Pop(S) //把棧頂元素彈出?，F(xiàn)在，我們?yōu)槎褩加一個(gè)新的操作，Multi-Pop(S,

k)。這個(gè)操作連續(xù)地把k個(gè)棧頂元素彈出。如果堆棧的元素個(gè)數(shù)少于k，則把所有元素彈出。這個(gè)操作可用下面的偽碼描述：(接下頁(yè))6例

17.1 堆棧操作(繼續(xù))Multi-Pop(S,

k) while

S

and

k>0

Pop(S)

k←k–1endwhileEnd假設(shè)堆棧S一開始是空的，算法要做總共n次的Push，或Pop，或Multi-Pop操作，總共需要多少時(shí)間呢？一個(gè)簡(jiǎn)單估計(jì)是，Multi-Pop最多需要O(n)時(shí)間，所以，最壞情況下，總共需要O(n2)時(shí)間。這個(gè)估計(jì)太松了。聚集法這樣分析：因?yàn)橐粋€(gè)元素必須先被壓入才可能被彈出，所以，Pop和Multi-Pop總共彈出的元素個(gè)數(shù)小于等于Push的操作次數(shù)。如果Push的次數(shù)是p，p

n，那么這n個(gè)操作總共需要的時(shí)間不超過(guò)O(p)+O(p)=O(n)。這就是為所有彈出的元素的個(gè)數(shù)算總帳的方法。7例17.2 有k位的二進(jìn)制計(jì)數(shù)器的連續(xù)增值數(shù)組A[0..k-1]對(duì)應(yīng)一個(gè)有k個(gè)比特的計(jì)數(shù)器，其中A[i](0

i

k-1)存儲(chǔ)一個(gè)二進(jìn)制比特，A[0]對(duì)應(yīng)最低位，A[k-1]對(duì)應(yīng)最高位。如果計(jì)數(shù)器中當(dāng)前的數(shù)是x，把它增值為x+1的做法是，從A[0]到A[k-1]，逐位檢查，如果該位是0，則把他翻轉(zhuǎn)為1，操作完成。否則，把該位從1翻轉(zhuǎn)為0后再檢查下一位。如果還是1，繼續(xù)把1翻轉(zhuǎn)為0，直到有一位是0為止。然后把0翻轉(zhuǎn)為1，操作完成。例如，把二進(jìn)制數(shù)1000111加1，我們需要把右邊3個(gè)1翻轉(zhuǎn)為0，再把下一個(gè)比特0翻轉(zhuǎn)為1，從而得到1001000。如果A[0..k-1]中每個(gè)比特都是1，那么再加1的話，計(jì)數(shù)器會(huì)歸零。即A[0..k-1]中每個(gè)比特都翻轉(zhuǎn)為0。這個(gè)計(jì)數(shù)器加1的過(guò)程可以用下面的算法實(shí)現(xiàn)。8例17.2 有k位的二進(jìn)制計(jì)數(shù)器的連續(xù)增值(繼續(xù)1)Increment(A) //輸入是數(shù)組A[0..k-1]k←length[A] //k=length[A]=計(jì)數(shù)器長(zhǎng)i←0whilei<k

and

A[i]=1

A[i]

0 i←i+1endwhileifi

<k //也就是i

k-1

thenA[i]

1endifEnd問題：

如果我們把計(jì)數(shù)器從0開始連續(xù)增值n次，n<2k，那么，我們需要多少時(shí)間可以完成呢？(接下頁(yè))9

10記賬法(accountingmethod)記賬法適用于有幾種不同的操作的情況。如果某種操作總共需要的時(shí)間始終比其他所有操作總共需要的時(shí)間大，那我們可以把賬全算在這個(gè)主要操作上。做法是：如果主要操作執(zhí)行一次需要一個(gè)單位時(shí)間，那么根據(jù)情況，我們把它算成2個(gè)單位時(shí)間，或3個(gè)單位時(shí)間，或某個(gè)常數(shù)c倍單位時(shí)間，稱為平攤時(shí)間(或平攤代價(jià))，而其他操作執(zhí)行一次的平攤時(shí)間置為0。這個(gè)主要操作每次多算的一個(gè)或幾個(gè)單位時(shí)間用來(lái)支付其他所有操作所需要的時(shí)間。顯然，在最壞情況下，不論有多少個(gè)主要操作和其他操作，平均一次操作的時(shí)間不會(huì)超過(guò)2個(gè)，或3個(gè)，或c個(gè)單位時(shí)間，從而得到O(n)的復(fù)雜度。11例

17.3 用計(jì)賬法分析堆棧操作因?yàn)镻op和Multi-Pop操作需要的總時(shí)間不會(huì)超過(guò)Push需要的總時(shí)間，所以我們?yōu)槊總€(gè)操作設(shè)置的平攤時(shí)間如下：Push:

平攤時(shí)間=2(單位時(shí)間)Pop: 平攤時(shí)間=0Multi-Pop：

平攤時(shí)間=0。那么，n次Push，Pop，和Multi-Pop操作需要的總時(shí)間可分析如下:總時(shí)間=Push

需要的總時(shí)間+Pop和Multi-Pop

需要的總時(shí)間Push需要的總時(shí)間+Push

需要的總時(shí)間

=2

Push

需要的總時(shí)間=2

(1

Push操作的次數(shù))=Push的平攤時(shí)間

Push操作的次數(shù)

2n =O(n)12例17.4 用計(jì)賬法分析有k位的二進(jìn)制計(jì)數(shù)器的連續(xù)增值因?yàn)橛?jì)數(shù)器開始為0，所以任一位上，每次把1翻轉(zhuǎn)為0之前必須先把0翻轉(zhuǎn)為1。這意味著，把0翻轉(zhuǎn)為1的次數(shù)大于等于把1翻轉(zhuǎn)為0的次數(shù)。我們?cè)O(shè)置平攤時(shí)間如下：把0翻轉(zhuǎn)為1：

平攤時(shí)間=2(單位時(shí)間)把1翻轉(zhuǎn)為0：

平攤時(shí)間=0。另外，從算法Increment(A)可知，每次增值把0翻轉(zhuǎn)為1的操作最多一次。所以，可平攤分析如下：增值n次的總時(shí)間=1

把0翻轉(zhuǎn)為1的次數(shù)+1

把1翻轉(zhuǎn)為0的次數(shù)

2

把0翻轉(zhuǎn)為1的次數(shù)=把0翻轉(zhuǎn)為1的平攤時(shí)間

把0翻轉(zhuǎn)為1的次數(shù)

2

n=O(n)13勢(shì)能法(potentialmethod)注意到，數(shù)據(jù)結(jié)構(gòu)進(jìn)行一次操作時(shí)，實(shí)際化費(fèi)的時(shí)間越長(zhǎng)，數(shù)據(jù)結(jié)構(gòu)的變化越大。勢(shì)能法(potentialmethod)試圖把兩者結(jié)合起來(lái)。做法：為數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)量定義一個(gè)勢(shì)能函數(shù)

。例如，堆棧中元素的個(gè)數(shù)定義為它的勢(shì)能，也可以把個(gè)數(shù)的兩倍定義為勢(shì)能等。勢(shì)能函數(shù)

要滿足兩個(gè)條件:設(shè)初始的數(shù)據(jù)量是D0，那么初始勢(shì)能為0，即

(D0)=0；在任何時(shí)刻i(即第i次操作后，i>0)，勢(shì)能函數(shù)大于等于0，即

(Di)

(D0)=0。(接下頁(yè))14

15

16例17.5(繼續(xù))如果第i次操作是Multi-Pop(S,k)，那么ci=min{s,k}。這里，s是堆棧S中的元素個(gè)數(shù)。因?yàn)槎褩５脑販p少ci個(gè)，

(Di)-

(Di-1)=-ci，所以平攤時(shí)間是ai=ci-ci=0。所以，用平攤時(shí)間得到的n次操作的復(fù)雜度是O(n)。顯然，堆棧中的元素個(gè)數(shù)不會(huì)大于n，

(Dn)

n，所以實(shí)際復(fù)雜度也是O(n)。例17.6 用勢(shì)能法分析有k位的二進(jìn)制計(jì)數(shù)器的連續(xù)增值我們定義有k位的二進(jìn)制計(jì)數(shù)器的勢(shì)能是它k位中數(shù)值為1的個(gè)數(shù)。因?yàn)橐婚_始每位都是0，因而有

(D0)=0。又因?yàn)檫@個(gè)數(shù)不可能是負(fù)數(shù)，所以

(Di)

(D0)成立。根據(jù)勢(shì)能法，堆棧操作的平攤時(shí)間可分析如下：(接下頁(yè))17例

17.6 (繼續(xù))假設(shè)第i次操作把h個(gè)最低位的值從1翻轉(zhuǎn)為0，然后把第h+1位的值從0翻轉(zhuǎn)為1。那么，實(shí)際操作時(shí)間是ci=h+1，因?yàn)樽隽薶+1次翻轉(zhuǎn)動(dòng)作。因?yàn)閿?shù)值為1的位數(shù)減少了(h-1)個(gè)，

(Di)-

(Di-1)=-(h–1)，所以平攤時(shí)間是ai=ci-(h–1)=(h+1)-(h–1)=2。顯然，用平攤時(shí)間，我們得到的n次操作的復(fù)雜度是O(n)。又因?yàn)?/p>

(Dn)

k<n，所以實(shí)際復(fù)雜度也是O(n)。18問題定義表格T由一系列存貯單元(slot)組成，每個(gè)單元可存貯一個(gè)數(shù)據(jù)。表格T擁有的存貯單元的個(gè)數(shù)稱為容量，記為size(T)，通常是2的指數(shù)，如210，212，220，等。表格T含有的數(shù)據(jù)的個(gè)數(shù)記為

number(T)。動(dòng)態(tài)存貯是，算法可隨時(shí)向表格插入一個(gè)數(shù)據(jù)或刪除一個(gè)數(shù)據(jù)。假設(shè)每插入或刪除一個(gè)數(shù)據(jù)需要一個(gè)單位時(shí)間的代價(jià)。動(dòng)態(tài)表格的容量隨數(shù)據(jù)多少而變化。一開始是一個(gè)小表格。隨著數(shù)據(jù)的增加，容量不夠時(shí)，則需要擴(kuò)張。反之，如果很多數(shù)據(jù)被刪除，表格中有大量閑置未用的單元時(shí)，則需要收縮以提高使用效率。每次擴(kuò)張或收縮必須是加倍或減半，保持容量是2的指數(shù)。(接下頁(yè))3.動(dòng)態(tài)表格19問題定義(繼續(xù))擴(kuò)張時(shí)，一個(gè)新的，容量加倍的表格會(huì)分配給算法，而老的表格會(huì)刪除，但必須先把數(shù)據(jù)從老表格復(fù)制到新表格中。這個(gè)操作需要的時(shí)間與復(fù)制的數(shù)據(jù)個(gè)數(shù)成正比。當(dāng)表格收縮減半時(shí)，一個(gè)新的，容量減半的表格會(huì)分配給算法使用。我們也必須把數(shù)據(jù)從老表格一個(gè)一個(gè)地復(fù)制到新表格中。這個(gè)操作需要的時(shí)間與復(fù)制的數(shù)據(jù)個(gè)數(shù)成正比。問題：如果從空表格開始，對(duì)一個(gè)表格進(jìn)行n次插入或刪除的操作，表格會(huì)經(jīng)歷多次擴(kuò)張或收縮，那么該怎樣分析這n次插入或刪除的復(fù)雜度呢？我們假定，分配一個(gè)新表格，只需常數(shù)時(shí)間，可忽略。我們只把數(shù)據(jù)的復(fù)制、插入、和刪除的次數(shù)記入時(shí)間復(fù)雜度。20只允許擴(kuò)張的動(dòng)態(tài)表格(一個(gè)簡(jiǎn)化的表格問題)這是個(gè)簡(jiǎn)單的動(dòng)態(tài)表格問題，它只允許插入操作，表格可多次擴(kuò)張，但沒有刪除，沒有收縮。表格T一開始為空，即size(T)=0，number(T)=0。表格填滿時(shí)，當(dāng)下一個(gè)要插入的新數(shù)據(jù)

x到來(lái)時(shí)，才把表格擴(kuò)張。擴(kuò)張的步驟如下：分配一個(gè)容量加倍的新表格把老表格中數(shù)據(jù)復(fù)制到新表格中，這個(gè)操作需要的時(shí)間與復(fù)制的數(shù)據(jù)個(gè)數(shù)成正比刪除老表格把新數(shù)據(jù)

x插入到新表格中?？梢?，表格在任何時(shí)刻都至少有一半的容量被數(shù)據(jù)填滿。(偽碼見下頁(yè))21Table-Insert(T,x) //向表格T插入數(shù)據(jù)xif

size(T)=0 //size(T)意味著T是空表格

then

T

anewtablewith1slot //分配容量為1的新表格 size(T)

1endif

//這時(shí)，數(shù)據(jù)x還沒有被插入，number(T)=0if

number(T)=size(T) //表格被填滿，需要擴(kuò)張 then T’

anewtablewith2

size(T)slots

//容量2

size(T)的新表格

table(T’)

table(T) //老表格中數(shù)據(jù)復(fù)制到新表格T’中

T

T’ //T的指針指向T’，T成為新表格 size(T)

2

size(T)endif //擴(kuò)張完成table(T)

x //把x插入到表格T中number(T)

number(T)+1

//數(shù)據(jù)個(gè)數(shù)加1End22算法Table-Insert分析如果第

i(1

i

n)次插入時(shí)，表格不滿，那么我們只需要一個(gè)單位時(shí)間即可，ci

=1。如果表格已滿，需要擴(kuò)張。這時(shí)必有size(T)=number(T)=2k，i=2k

+1，這里，k是某個(gè)正整數(shù)，2k

是老表格里的數(shù)據(jù)個(gè)數(shù)。因此，擴(kuò)張需要2k

個(gè)單位時(shí)間來(lái)復(fù)制數(shù)據(jù)。所以，當(dāng)

i

=2k

+1時(shí)，第i次插入操作實(shí)際需要時(shí)間是ci

=1+2k

=i。用最壞情況

ci

=i

來(lái)估計(jì)n次插入的復(fù)雜度，我們會(huì)得到

1+2+…+n=O(n2)的結(jié)果。這個(gè)結(jié)果太大了。用平攤分析，可得到O(n)的復(fù)雜度，分析如下。(接下頁(yè))23算法Table-Insert分析(繼續(xù)1)聚集法：擴(kuò)張只在i=2k+1時(shí)發(fā)生(k=0,1,…)，所以，n次插入的復(fù)雜度是:擴(kuò)張需要的總時(shí)間+n次新數(shù)據(jù)的插入的時(shí)間

==(1+2+…+2k

)+n<2

2k+n

2n

+n=3n。計(jì)賬法：每次新數(shù)據(jù)插入的平攤時(shí)間記為3(單位時(shí)間)。數(shù)據(jù)復(fù)制的平攤時(shí)間記為0。因?yàn)閿U(kuò)張需要的總時(shí)間=(1+2+…+2k

)

<2n，所以每次新數(shù)據(jù)的插入多算的2個(gè)單位時(shí)間足夠支付所有擴(kuò)張所需要的總時(shí)間。因此，n次插入操作的復(fù)雜度是3n

=或O(n)。勢(shì)能法：(接下頁(yè))24算法Table-Insert分析(繼續(xù)2)勢(shì)能法：

定義勢(shì)能函數(shù)

(T)=2

number(T)-size(T)。這里，number(T)是表格含有的數(shù)據(jù)個(gè)數(shù)，size(T)是表格的容量。Ti表示第i個(gè)數(shù)據(jù)插入后的表格(i=0,1,2,…)。初始表格T0為空。number(T0)=size(T0)=0，從而有

(T0)=0。因?yàn)門i中至少一半的容量有數(shù)據(jù)，2

number(Ti)-size(Ti)

0。這個(gè)勢(shì)能函數(shù)

(T)滿足定義要求的兩個(gè)條件。

讓我們用這個(gè)勢(shì)能函數(shù)來(lái)計(jì)算平攤時(shí)間。如第i次插入不需要擴(kuò)張，那么有size(Ti)=size(Ti-1)。因?yàn)?/p>

(Ti)-

(Ti-1)=2。因每次插入實(shí)際需要時(shí)間是

ci=1，得到平攤時(shí)間

ai

=ci

+2=1+2=3。(接下頁(yè))25算法Table-Insert分析(繼續(xù)3)勢(shì)能法

(繼續(xù))：(B) 如第

i次插入需要擴(kuò)張，那么number(Ti-1)=size(Ti-1)=i–1。所以，第

i次插入前，

(Ti-1)=2

number(Ti-1)-size(Ti-1)=i-1。第i次插入后，number(Ti)=i，size(Ti)=2(i–1)，因此有

(Ti)=2

number(Ti)-size(Ti)=2i-2(i–1)=2。因?yàn)閺?fù)制需要i–1個(gè)單位時(shí)間，加上插入第i個(gè)數(shù)據(jù)需要的1個(gè)單位時(shí)間，所以第i次插入實(shí)用時(shí)間是ci

=i。所以，平攤時(shí)間是：ai

=ci

+

(Ti)-

(Ti-1)=i+[2–(i–1)]=3。以上說(shuō)明，不論第i次插入需不需要擴(kuò)張，它的平攤時(shí)間都是ai

=3。所以，n次插入操作的平攤復(fù)雜度是3n=O(n)。因?yàn)?/p>

(Tn)=2

number(Tn)-size(Tn)

number(Tn)=n，所以

n次插入操作的實(shí)際復(fù)雜度也是O(n)。26擴(kuò)張和收縮都有的動(dòng)態(tài)表格規(guī)定每次擴(kuò)張使容量加倍，而每次收縮使容量減半。插入算法同上一節(jié)。問題：是什么情形下，我們認(rèn)為有太多的閑置單元而收縮呢？用裝填因子來(lái)衡量，定義為number(T)/size(T)。用裝填因子0.5作為收縮的標(biāo)準(zhǔn)，行嗎？不行!看一例子。設(shè)當(dāng)前

size(T)=2k

和

number(T)=2k-1。如果下兩個(gè)操作是插入，那么，在插入第1個(gè)數(shù)后，表格需要擴(kuò)張后插入第2個(gè)數(shù)，總共用時(shí)2k+2單位時(shí)間。這時(shí)，number(T)=2k+1，size(T)=2k+1。如果下兩個(gè)操作是刪除，刪除后number(T)=2k-1，裝填因子<0.5，需要在刪除第1個(gè)數(shù)后收縮，總共用時(shí)也是2k+2。

這時(shí)，表格恢復(fù)到操作前狀態(tài)，size(T)=2k

和number(T)=2k-1。(接下頁(yè))27擴(kuò)張和收縮都有的動(dòng)態(tài)表格(繼續(xù))如果接下去有一系列的插入2個(gè)和刪除2個(gè)的操作，那么平均一次操作的時(shí)間是(2k+2)/2=2k-1+1。因?yàn)閗不保證是常數(shù)，所以，用0.5或接近0.5的裝填因子作為表格收縮的標(biāo)準(zhǔn)不可能保證平均一次操作的時(shí)間是常數(shù)。上面的例子使我們相信，合理的裝填因子是0.25。0.25倍的容量仍然是2的指數(shù)。另外，太小的裝填因子會(huì)降低表格的空間利用率。下面是以裝填因子=0.25而設(shè)計(jì)的刪除算法。它與插入一個(gè)數(shù)的算法很類似。有一個(gè)小細(xì)節(jié)要注意。當(dāng)刪除一個(gè)數(shù)導(dǎo)致表格收縮時(shí)，我們先刪除這個(gè)數(shù)，再收縮，而不是先收縮，再刪除。否則，這個(gè)數(shù)會(huì)在刪除前，被不必要地復(fù)制一次。因一個(gè)數(shù)據(jù)先有插入才會(huì)有刪除，故任何時(shí)候，刪除操作的次數(shù)

插入操作的個(gè)數(shù)。(偽碼見下頁(yè))28Table-Delete(T,x) //從表格T刪除一個(gè)數(shù)據(jù)x，設(shè)表格T非空Loading-factor(T)

number(T)/size(T)table(T)

table(T)–{x} //把x刪除，Loading-factor(T)不變number(T)

number(T)-1if

Loading-factor(T)

0.25 //這是刪除x前的Loading-factor

then

T’

anewtablewith0.5

size(T)slots //容量減半

table(T’)

table(T) //把T中數(shù)據(jù)復(fù)制到新表格T’中

T

T’ //讓T的指針指向新表格T’

size(T)

0.5

size(T)endif //收縮完成End平攤分析n次插入和刪除的操作的復(fù)雜度用聚集法或計(jì)帳法難有直觀的結(jié)果。我們用勢(shì)能法。(接下頁(yè))29平攤分析n次插入和刪除的操作的復(fù)雜度(繼續(xù))我們?cè)O(shè)計(jì)如下的勢(shì)能函數(shù)：當(dāng)Loading-factor(T)

0.5時(shí)，

(T)=2

number(T)-size(T)，否則，

(T)=0.5

size(T)-number(T)。一開始，表格為空，number(T)=size(T)=0，

(T0)=0。又因?yàn)椋?dāng)Loading-factor(T)

0.5時(shí)，

(T)=2

number(T)-size(T)

0，當(dāng)Loading-factor(T)<0.5時(shí)，

(T)=0.5

size(T)-number(T)>0，

所以

(T)滿足勢(shì)能函數(shù)定義的2個(gè)要求?，F(xiàn)在，我們來(lái)分析一下，一次插入或刪除的平攤時(shí)間是多少。A. 第

i次操作是插入這時(shí)表格不收縮，可能擴(kuò)張。兩種情況，分述如下。(接下頁(yè))30第

i次操作是插入(繼續(xù)1)A.1 在插入時(shí)，Loading-factor(Ti-1)

0.5。這時(shí)，表格也許會(huì)擴(kuò)張，因?yàn)椴迦肭昂筒迦牒笏脛?shì)能函數(shù)都是

(T)=2

number(T)-size(T)，所以平攤時(shí)間的分析與前一節(jié)對(duì)Table-Insert的分析一樣，平攤時(shí)間是

ai

=3。A.2

在插入時(shí)，Loading-factor(Ti-1)<0.5。如果插入后，仍有Loading-factor(Ti)<0.5，

那么因?yàn)?/p>

size(Ti)=size(Ti-1)，前后的勢(shì)能函數(shù)不變，我們有：ai

=ci

+

(Ti)-

(Ti-1)=ci

+[0.5

size(Ti)-number(Ti)]-[0.5

size(Ti-1)-number(Ti-1)]=1–1

=0(接下頁(yè))31A.2 在插入時(shí)，Loading-factor(Ti-1)<0.5。(繼續(xù))如果插入后Loading-factor(Ti)=0.5，那么因?yàn)?/p>

size(Ti)=size(Ti-1)，我們有：ai

=ci

+

(Ti)-

(Ti-1)=ci

+[2

number(Ti)-size(Ti)]-[0.5

size(Ti-1)-number(Ti-1)]=1+2[number(Ti-1)+1]-size(Ti)-0.5

size(Ti-1)+number(Ti-1)=3+3number(Ti-1)–1.5size(Ti-1)=0

//因?yàn)閚umber(Ti-1)+1=0.5size(Ti-1) B. 第

i次操作是刪除這時(shí)表格不擴(kuò)張，但可能收縮。也有兩種情況，分述如下。B.1

在刪除時(shí)，Loading-factor(Ti-1)

0.5。這時(shí)，表格不會(huì)收縮，但Loading-factor(Ti)可能小于

0.5。(接下頁(yè))32第

i次操作是刪除(繼續(xù)1)B.1

在刪除時(shí)，Loading-factor(Ti-1)

0.5。(繼續(xù))如果Loading-factor(Ti)

0.5，我們有：ai

=ci

+

(Ti)-

(Ti-1)=1+[2

number(Ti)-size(Ti)]-[2

number(Ti-1)-size(Ti-1)]=1+2=3如果Loading-factor(Ti)<0.5，我們必有

Loading-factor(Ti-1)=0.5和

number(Ti-1)=0.5size(Ti-1)=0.5size(Ti)。所以有：ai

=ci

+

(Ti)-

(Ti-1)=1+[0.5

size(Ti)-number(Ti)]-[2

number(Ti-1)-size(Ti-1)]=1+0.5

size(Ti)–[number(Ti-1)–1]-2

number(Ti-1)+size(Ti-1)=2(接下頁(yè))33第

i次操作是刪除(繼續(xù)2

)B.2

在刪除時(shí)，Loading-factor(Ti-1)<0.5。如果表格不收縮，size(Ti)=size(Ti-1)，我們有:ai

=ci

+

(Ti)-

(Ti-1)=1+[0.5

size(Ti)-number(Ti)]-[0.5

size(Ti-1)-number(Ti-1)]=1+1=2(2) 如果表格收縮，我們有

size(Ti)=0.5size(Ti-1)，number(Ti-1)=0.25size(Ti-1)。所以有：ai

=ci

+

(Ti)-

(Ti-1)=0.25size(Ti-1)+[0.5

size(Ti)-number(Ti)]-[0.5

size(Ti-1)-number(Ti-1)]

=0.25size(Ti-1)+0.25size(Ti-1)–[number(Ti-1)–1]-0.5

size(Ti-1)+number(Ti-1)

=134第

i次操作是刪除(繼續(xù)3)以上說(shuō)明，不論第

i次操作是插入還是刪除，需不需要擴(kuò)張和收縮，它的平攤時(shí)間都不超過(guò)3，所以，動(dòng)態(tài)表格的n次插入和刪除操作的平攤復(fù)雜度是O(n)。顯然，它的實(shí)際復(fù)雜度也是O(n)，這是因?yàn)椋寒?dāng)Loading-factor(Tn)

0.5時(shí)，

(Tn)=2

number(Tn)-size(Tn)

number(Tn)

n。當(dāng)Loading-factor(Tn)<0.5時(shí)，

(Tn)=0.5

size(Tn)-number(Tn)

0.5

[4

number(Tn)]-number(Tn)

2number(Tn)-number(Tn)=number(Tn)

n。354.斐波那契堆第3章的最小堆或最大堆需要O(lgn)時(shí)間更新一個(gè)數(shù)。斐波那契堆把更新操作改進(jìn)為平攤復(fù)雜度O(1)，從而改進(jìn)Prim算法和Dijkstra算法的復(fù)雜度為O(nlgn+m)。斐波那契堆還能方便地插入一個(gè)數(shù)據(jù)，刪去一個(gè)數(shù)據(jù)，以及合并兩個(gè)堆為一個(gè)堆。為區(qū)別起見，以前討論的堆稱為二叉堆。斐波那契堆也有最小和最大兩種。因?yàn)樗鼈兪菍?duì)稱的概念，我們只討論最小斐波那契堆，即父親的關(guān)鍵字小于等于兒子的關(guān)鍵字。下面的表把二叉堆和斐波那契堆作了簡(jiǎn)明比較。表中列出，對(duì)于各種可能用到的基本操作，這兩種數(shù)據(jù)結(jié)構(gòu)需要的時(shí)間復(fù)雜度。(見下頁(yè))36表17-1

最小二叉堆和最小斐波那契堆對(duì)基本操作的復(fù)雜度比較操作二叉堆最壞情況復(fù)雜度斐波那契堆平攤復(fù)雜度建一空堆(Make-Heap)

(1)

(1)插入(Insert)

(lgn)

(1)獲取最小值(Minimum)

(1)

(1)摘取最小值(Extract-Min)

(lgn)

(lgn)合并(Union)

(n)

(1)減小關(guān)鍵字(Decrease-Key)

(lgn)

(1)刪除(Delete)

(lgn)

(lgn)表17-1中前5個(gè)操作稱為可合并堆的操作。37斐波那契堆的結(jié)構(gòu)斐波那契堆H中的每一個(gè)結(jié)點(diǎn)x存有一個(gè)數(shù)據(jù)。它有以下屬性：

x.key

關(guān)鍵字，是主要屬性。此外，還含有以下屬性：x.p

指向父親的指針。如果x是某個(gè)樹根，x.p=nilx.degree

點(diǎn)x的兒子個(gè)數(shù)。如果沒有兒子，x.degree=0因?yàn)槊總€(gè)結(jié)點(diǎn)的所有兒子也用雙向指針鏈結(jié)為一個(gè)環(huán)，因此有：x.left 指向點(diǎn)x左邊的兄弟的指針x.right 指向點(diǎn)x右邊的兄弟的指針x.child 指向x的某個(gè)兒子的指針，可任取一個(gè)，稱為長(zhǎng)子如果x在樹根環(huán)中，x.left和x.right也用來(lái)與它的相鄰數(shù)根鏈結(jié)。x.mark 是個(gè)布爾變量，稱作標(biāo)記。x.mark=true表示x成為當(dāng)前父親的兒子后有兒子被切走。否則x.mark=false。(如果x是新建的點(diǎn)，也置x.mark

=false。)38斐波那契堆的結(jié)構(gòu)

(繼續(xù))斐波那契堆H的屬性：H.n

表示堆H中有幾個(gè)關(guān)鍵字。如果堆為空，H.n=0。H.min 指向樹根環(huán)中關(guān)鍵字最小的根。如果是空堆，H.min=nil。任一結(jié)點(diǎn)中的數(shù)字(關(guān)鍵字)小于等于它的任一個(gè)兒子結(jié)點(diǎn)中的數(shù)字。14H.min1736242854192933491920H.n=13例(圖17-1)39為清晰簡(jiǎn)明，我們用下圖(17-2)來(lái)表示上面圖中的斐波那契堆。14H.min1736242854192933491920H.n=13為了作平攤分析，我們定義斐波那契堆的勢(shì)能函數(shù)為：

(H)=t(H)+2m(H)其中，t(H)=樹根表中樹的個(gè)數(shù)，m(H)=有標(biāo)記的點(diǎn)的個(gè)數(shù)。例如，上面圖中的斐波那契堆的勢(shì)能函數(shù)是

(H)=4+2

4=12。顯然，這個(gè)定義滿足勢(shì)能函數(shù)的兩個(gè)條件。如果算法同時(shí)使用幾個(gè)斐波那契堆，那么，它們的總勢(shì)能是各個(gè)斐波那契堆的勢(shì)能之和。40斐波那契堆中最大的度下面的討論需要用到一個(gè)結(jié)果：有n個(gè)結(jié)點(diǎn)的堆中，任一個(gè)點(diǎn)x的度，即x.degree，有個(gè)上界。D(n)表示有n個(gè)結(jié)點(diǎn)的斐波那契堆中最大的度?？勺C明

D(n)=O(lgn)。我們先用上這個(gè)結(jié)果。所有操作討論完之后，我們證明這個(gè)上界?？珊喜⒍训牟僮魑覀兿扔懻摽珊喜⒍训牟僮鳎幢?7-1中前5個(gè)操作A. Make-Fib-Heap(H)這個(gè)操作建立一個(gè)空堆H，其中一個(gè)關(guān)鍵字也沒有。我們只要求系統(tǒng)分配一個(gè)存儲(chǔ)單元后返回一個(gè)對(duì)象H。它的屬性是H.n=0,H.min=nil，樹根表為空。這個(gè)斐波那契堆的勢(shì)能為0，

(H)=0。這個(gè)操作的實(shí)用時(shí)間及平攤時(shí)間均可置為O(1)。41可合并堆的操作(繼續(xù)1)Fib-Heap-Insert(H,x)這個(gè)操作是在堆H中插入一個(gè)新點(diǎn)x。我們假定，數(shù)據(jù)對(duì)象x已建立，它的屬性x.key已有。這個(gè)操作很簡(jiǎn)單，我們建立一個(gè)只含x的樹后，把它插入到H的樹根表中。下面是偽碼。Fib-Heap-Insert(H,x)x.degree

0x.p

nilx.child

nilx.mark

false(接下頁(yè))42可合并堆的操作(繼續(xù)2)if

H.min=nil

//如果樹根表為空

then

createarootlistcontainingjustx //建只含x的樹根表

H.min

x

elseinsertxintoH’srootlist //否則，把x插入到H的樹根表

if

x.key<H.min.key

then

H.min

x //更新H.min

endifendifH.n

H.n+1End該操作實(shí)用時(shí)間為O(1)。它不增減標(biāo)記，但增加1個(gè)樹根表中的樹，故勢(shì)能函數(shù)加1。所以這個(gè)操作的平攤時(shí)間為O(1)+1=O(1)。43可合并堆的操作(繼續(xù)3)C. Minimum(H)這個(gè)操作獲取斐波那契堆H中的最小關(guān)鍵字。因?yàn)橹羔楬.min直接指向有最小關(guān)鍵字的點(diǎn)，這個(gè)操作需要的實(shí)用時(shí)間為O(1)。因?yàn)檫@個(gè)操作不改變堆的結(jié)構(gòu)和勢(shì)能，所以這個(gè)操作的平攤時(shí)間為O(1)+0=O(1)。D. Fib-Heap-Union(H,H1,H2)這個(gè)操作把兩個(gè)斐波那契堆，H1和H2，合并為一個(gè)斐波那契堆。就是把這兩個(gè)堆中的點(diǎn)不增不減地組成一個(gè)堆H，完成后，刪除H1和H2。下面是偽碼。Fib-Heap-Union(H,H1,H2)Make-Fib-Heap(H)H.min

H1.min //相當(dāng)于把H1改名為

H

(接下頁(yè))44可合并堆的操作(繼續(xù)4)concatenatetherootlistofH2withtherootlistofH

//把H2的樹根表并入H的樹根表ifH.min=nil

then

H.min

H2.min

else if(H2.min

nil)and(H2.min.key<H.min.key)

thenH.min

H2.min //更新H的最小關(guān)鍵字

endifendifH.n=H1.n+H2.n

return

HEnd因?yàn)槊恳徊蕉贾灰狾(1)的時(shí)間，這個(gè)操作的實(shí)用時(shí)間為O(1)。因?yàn)閠(H)=t(H1)+t(H2)，而且不改變標(biāo)記數(shù)，所以勢(shì)能的變化為0，這個(gè)合并操作的平攤時(shí)間為O(1)+0=O(1)。45可合并堆的操作(繼續(xù)5)Fib-Heap-Extract-Min(H)這個(gè)操作摘取堆中最小點(diǎn)，是最復(fù)雜的一個(gè)操作，因?yàn)榘袶.min指向的點(diǎn)刪除以后，我們要對(duì)余下的堆進(jìn)行修復(fù)。修復(fù)分3步。第一步把最小點(diǎn)的所有兒子逐一插入到H的樹根表中。第二步刪除最小點(diǎn)。第三步對(duì)樹根表中的點(diǎn)進(jìn)行合并調(diào)整使得每個(gè)樹根的度都不同，同時(shí)建立新的樹根表和指向新的最小點(diǎn)的指針。這一步的工作由子程序Consolidate(H)完成。我們先給出摘取最小點(diǎn)操作的主程序的偽碼，然后給出Consolidate(H)的偽碼。46可合并堆的操作(繼續(xù)6)Fib-Heap-Extract-Min(H) z

H.min //z指向最小點(diǎn)ifz

nil

then

for

eachchildxofz

addxtotherootlistofH //把x插入樹根表

x.p

nil

endfor

removezfromtherootlistofH

//摘除最小點(diǎn)

if

z=z.right

//原樹根表只有最小點(diǎn)

then

H.min

nil

else

H.min

z.right

//暫取原根表中下一個(gè)，需調(diào)整

Consolidate(H) //做合并調(diào)整的子程序

endif

H.n

H.n-1

(接下頁(yè))47可合并堆的操作(繼續(xù)7) return

z

else

return

(error,emptyheap)endifEnd.下面討論子程序Consolidate(H)。它的主要工作是檢查樹根表中每個(gè)點(diǎn)的度是否都不同。一旦發(fā)現(xiàn)樹根x和樹根y的度相同，則把它們合并。具體作法是：如果x.key

y.key，那么：把樹根y從樹根表中摘除并把它作為兒子接到樹根x的兒子鏈表中。樹根x的度要加1，即x.degree

x.degree+1。如果點(diǎn)y有標(biāo)記，則要改置為false。

這個(gè)簡(jiǎn)單的操作用子程序Fib-Heap-Link(H,y,x)來(lái)實(shí)現(xiàn)。

(接下頁(yè))48可合并堆的操作(繼續(xù)8)Fib-Heap-Link(H,y,x)removeyfromtherootlistofHmakeyachildofx //把樹根y插入到樹根x的兒子環(huán)中，y.p

xx.degree

x.degree+1y.mark

falseEnd下面繼續(xù)討論子程序Consolidate(H)。該子程序通過(guò)一系列Fib-Heap-Link的合并操作使樹根表中每個(gè)樹根的度都不同。我們先建一個(gè)數(shù)組A[0..D]，其中A[k](0

k

D)，是用來(lái)指向度為k的樹根的指針，D

=D(n)是當(dāng)前斐波那契堆中所有點(diǎn)的最大度數(shù)。一開始，A[k]=nil(0

k

D)。然后，逐個(gè)檢查樹根表中的樹根。(接下頁(yè))49可合并堆的操作(繼續(xù)9)假設(shè)當(dāng)前檢查的樹根x的度是k。操作如下：如果A[k]=nil，則置A[k]

x，程序Consolidate結(jié)束。如果A[k]=y

nil，則調(diào)用Fib-Heap-Link合并樹根x和y。合并后，把A[k]置為nil。合并后的樹根

z

有度k+1。把樹根

z作為當(dāng)前檢查的樹根x，k

k+1，重復(fù)(1)(2)。顯然，這個(gè)合并的次數(shù)不會(huì)超過(guò)D=O(lgn)次。完成上述對(duì)樹根的合并后，子程序Consolidate(H)把數(shù)組A[0..D]中非空指針?biāo)赶虻臉涓橐粋€(gè)新的樹根表，并找出新的最小點(diǎn)。這時(shí)，子程序Consolidate(H)就完成了，摘取堆中最小點(diǎn)的操作Fib-Heap-Extract-Min(H)也隨之完成。下面是Consolidate(H)的偽碼。(接下頁(yè))50Consolidate(H)for

k

0to

D //D

=D(H.n)

A[k]

nil //初始化A[0..D]endforforeachnodewintherootlistofH

//可認(rèn)為從H.min開始

x

w，d

x.degree

while

A[d]

nil

y

A[d]

ifx.key>y.key

then

x

y //指針x和y交換使y.key

x.key

endif

Fib-Heap-Link(H,y,x)

A[d]

nil，d

d+1

endwhile A[d]

xendfor

(接下頁(yè))51Consolidate

(繼續(xù))

H.min

nil //由A[0..D]構(gòu)造樹根表for

i

0to

D

ifA[i]

nil

then

ifH.min=nil //插入第一個(gè)樹根

thencreatearootlistforHcontainingjustA[i]

H.min

A[i]

elseinsertA[i]intoH’srootlist

if

A[i].key<H.min.key

thenH.min

A[i]

endif

endif

endifendforEnd52看一個(gè)例子。假設(shè)要把圖(17-1)中最小點(diǎn)刪除。第一步把最小點(diǎn)的兒子并入樹根表，第二步把最小點(diǎn)摘除，下圖(17-3)是第二步之后，第三步之前的情況。第三步是調(diào)用Consolidate(H)進(jìn)行合并調(diào)整。14H.min1736419294933202428195336(b)

下一個(gè)點(diǎn)17的度是2，,聯(lián)到A[2]36

(a)

H.min指向的點(diǎn)19的度是1，聯(lián)到A[1]94133191714204929240123Aw,x2894133191714204929240123A28w,x36(c)

下一個(gè)點(diǎn)14的度是0，聯(lián)到A[0]94133191714204929240123A28w,x369413317142049290123A192428w,x(d)點(diǎn)9的度是1，與點(diǎn)19合并540123A93314492936172041192428w,x(e)點(diǎn)9與點(diǎn)17合并，清除點(diǎn)17標(biāo)記，聯(lián)到A[3]0123A14334941929361720192428x(f)點(diǎn)41度為0，與點(diǎn)14合并后聯(lián)到A[1]w0123A14334941x(g)

點(diǎn)33度為1，并入點(diǎn)14后聯(lián)到A[2]92936172019242814334941H.min(h)

合并調(diào)整后的斐波那契堆929361720192428wH.n=1255摘取最小點(diǎn)的平攤分析實(shí)際使用的時(shí)間。主程序Fib-Heap-Extract-Min(H)的主要工作是把最小點(diǎn)的兒子插入樹根表，然后摘取最小點(diǎn)。因?yàn)槿魏吸c(diǎn)的度

D(n)，所以，這部分實(shí)際使用時(shí)間是O(D(n))。操作前，樹根表規(guī)模是t(H)，操作后，樹根表規(guī)模

t(H)

)+D(n)。子程序Consolidate(H)的主要工作是逐個(gè)檢查樹根表里的樹根，如果發(fā)現(xiàn)兩個(gè)樹根x和y有相同的度，則用Fib-Heap-Link將它們合并。因?yàn)闃涓碛凶疃鄑(H)+D(n)個(gè)點(diǎn)，而每調(diào)用Fib-Heap-Link一次，樹根表中的點(diǎn)就減少一個(gè)，所以這樣的合并不超過(guò)t(H)+D(n)次。因此，子程序Consolidate(H)的實(shí)用時(shí)間是O(t(H)+D(n))。這也是摘取最小點(diǎn)需要的總的實(shí)用時(shí)間。(接下頁(yè))56摘取最小點(diǎn)的平攤分析(繼續(xù))勢(shì)能的變化。設(shè)m(H)為刪除最小點(diǎn)之前有標(biāo)記點(diǎn)的個(gè)數(shù)，那么刪除最小點(diǎn)之前的勢(shì)能是t(H)+2m(H)。因?yàn)閯h除最小點(diǎn)的過(guò)程不增加有標(biāo)記的點(diǎn)，而刪除最小點(diǎn)之后的樹根表中的樹根個(gè)數(shù)最多是D(n)+1個(gè)，所以勢(shì)能的增量最多是[D(n)+1-t(H)]。綜合(1)(2)，摘取最小值的平攤時(shí)間是O(t(H)+D(n))+D(n)+1-t(H)=O(D(n))=O(lgn)注評(píng)：括號(hào)里的t(H)和括號(hào)外的t(H)對(duì)消，是因?yàn)槔ㄌ?hào)外的t(H)是勢(shì)能部分。我們可把它乘以一個(gè)大的常數(shù)去抵消括號(hào)里的t(H)，即把勢(shì)能定義為C(t(H)+2m(H))。這里，C是一個(gè)足夠大的常數(shù)。57減小一個(gè)關(guān)鍵字和刪除任一結(jié)點(diǎn)的操作在這一節(jié)，我們討論表17-1中后2個(gè)操作。A. Fib-Heap-Decrease-Key(H,x,k)(把結(jié)點(diǎn)x的關(guān)鍵字減小為k）假設(shè)我們要把點(diǎn)x中的關(guān)鍵字x.key減小到k，操作步驟如下：如果k>x.key，報(bào)告出錯(cuò)，因?yàn)樾碌闹祂比x.key還大。把x.key

置為新的值k，即x.key

k。如果點(diǎn)x是一個(gè)樹根，或者x.key

y.key，則跳過(guò)(4)，這里，點(diǎn)y是點(diǎn)x的父親。如果點(diǎn)x不是樹根并且x.key<y.key，調(diào)用子程序Cascading-Cut(H,x,y)。如果k<H.min.key，則更新H.min為x，H.min

x。操作完成。(接下頁(yè))58A. Fib-Heap-Decrease-Key(繼續(xù)1)子程序Cascading-Cut(H,x,y)是個(gè)遞歸程序，稱為連續(xù)切割。它把結(jié)點(diǎn)x為根的樹從父親結(jié)點(diǎn)y切下后，插入到樹根環(huán)中。這時(shí)，如果父親y不在樹根環(huán)中，并且有標(biāo)記，則把

y為根的樹從

y的父親

z切下后，插入到樹根環(huán)中。繼續(xù)這個(gè)連續(xù)切割的過(guò)程，直到切下的點(diǎn)的父親w已經(jīng)在樹根環(huán)里，或者w沒有標(biāo)記，為止。這個(gè)子程序的第1步是為了糾正堆順序，使兒子

x的關(guān)鍵字大于等于父親的關(guān)鍵字；第2步及以后每步是保證每個(gè)點(diǎn)最多被切去一個(gè)兒子，除非它在樹根環(huán)中。下面我們先給出主程序Fib-Heap-Decrease-Key的偽碼，隨后給出子程序Cascading-Cut(H,x,y)的偽碼。59Fib-Heap-Decrease-Key(繼續(xù)2)Fib-Heap-Decrease-Key(H,x,k)if

k>x.key

thenreturn(Error,newkeyisgreaterthancurrentkey.)endifx.key

ky

x.pify

nil

and

x.key<y.key thenCascading-Cut(H,x,y) //該子程序偽碼在下面。endif

ifx.key<H.min.key thenH.min

xendifEnd下面是子程序Cascading-Cut(H,x,y)偽碼。60Fib-Heap-Decrease-Key(繼續(xù)3)Cascading-Cut(H,x,y)removexfromthechildlistofy //把x從y的兒子環(huán)中移開y.degree

y.degree–1ify.child=x //如果x是y的長(zhǎng)子

then

ifx.right≠x

//如果x不是y的唯一的兒子

then

y.child

x.right //重設(shè)y的長(zhǎng)子

else

y.child

nil

endifendifaddxtotherootlistofH

//把x加到H的樹根表中

x.p

nilx.mark

false //取消標(biāo)記(接下頁(yè))61Fib-Heap-Decrease-Key(繼續(xù)4)Cascading-Cut

(繼續(xù))z

y.pifz

nil

//如果y是個(gè)樹根，失去兒子x后不改變標(biāo)記 thenif

y.mark=false //如果y不是樹根且無(wú)標(biāo)記

then

y.mark

true//則失去x打標(biāo)記，算法完成

else

Cascading-Cut(H,y,z) //否則，繼續(xù)切割

endifendifEnd下面圖(17-5)給出了一個(gè)例子。6224374231H.min(a) 操作前的堆。下面要把22減少為682636151929342224374231H.min82