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

1第17

章

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

2平攤分析的常用方法

5動態(tài)表格

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

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

26斐波那契堆

35可合并堆的操作

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

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

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

k)。這個操作連續(xù)地把k個棧頂元素彈出。如果堆棧的元素個數(shù)少于k，則把所有元素彈出。這個操作可用下面的偽碼描述：(接下頁)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操作，總共需要多少時間呢？一個簡單估計是，Multi-Pop最多需要O(n)時間，所以，最壞情況下，總共需要O(n2)時間。這個估計太松了。聚集法這樣分析：因為一個元素必須先被壓入才可能被彈出，所以，Pop和Multi-Pop總共彈出的元素個數(shù)小于等于Push的操作次數(shù)。如果Push的次數(shù)是p，p

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

i

k-1)存儲一個二進制比特，A[0]對應(yīng)最低位，A[k-1]對應(yīng)最高位。如果計數(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，操作完成。例如，把二進制數(shù)1000111加1，我們需要把右邊3個1翻轉(zhuǎn)為0，再把下一個比特0翻轉(zhuǎn)為1，從而得到1001000。如果A[0..k-1]中每個比特都是1，那么再加1的話，計數(shù)器會歸零。即A[0..k-1]中每個比特都翻轉(zhuǎn)為0。這個計數(shù)器加1的過程可以用下面的算法實現(xiàn)。8例17.2 有k位的二進制計數(shù)器的連續(xù)增值(繼續(xù)1)Increment(A) //輸入是數(shù)組A[0..k-1]k←length[A] //k=length[A]=計數(shù)器長i←0whilei<k

and

A[i]=1

A[i]

0 i←i+1endwhileifi

<k //也就是i

k-1

thenA[i]

1endifEnd問題：

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

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

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

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

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

需要的總時間+Pop和Multi-Pop

需要的總時間Push需要的總時間+Push

需要的總時間

=2

Push

需要的總時間=2

(1

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

Push操作的次數(shù)

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

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

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

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

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

2

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

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

2

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

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

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

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

(Di)

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

15

16例17.5(繼續(xù))如果第i次操作是Multi-Pop(S,k)，那么ci=min{s,k}。這里，s是堆棧S中的元素個數(shù)。因為堆棧的元素減少ci個，

(Di)-

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

(Dn)

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

(D0)=0。又因為這個數(shù)不可能是負(fù)數(shù)，所以

(Di)

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

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

(Di)-

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

(Dn)

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

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

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

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

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

then

T

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

1endif

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

number(T)=size(T) //表格被填滿，需要擴張 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 //擴張完成table(T)

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

number(T)+1

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

i(1

i

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

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

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

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

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

i

=2k

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

=1+2k

=i。用最壞情況

ci

=i

來估計n次插入的復(fù)雜度，我們會得到

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

==(1+2+…+2k

)+n<2

2k+n

2n

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

)

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

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

定義勢能函數(shù)

(T)=2

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

(T0)=0。因為Ti中至少一半的容量有數(shù)據(jù)，2

number(Ti)-size(Ti)

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

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

讓我們用這個勢能函數(shù)來計算平攤時間。如第i次插入不需要擴張，那么有size(Ti)=size(Ti-1)。因為

(Ti)-

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

ci=1，得到平攤時間

ai

=ci

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

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

i次插入需要擴張，那么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。因為復(fù)制需要i–1個單位時間，加上插入第i個數(shù)據(jù)需要的1個單位時間，所以第i次插入實用時間是ci

=i。所以，平攤時間是：ai

=ci

+

(Ti)-

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

=3。所以，n次插入操作的平攤復(fù)雜度是3n=O(n)。因為

(Tn)=2

number(Tn)-size(Tn)

number(Tn)=n，所以

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

size(T)=2k

和

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

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

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

插入操作的個數(shù)。(偽碼見下頁)28Table-Delete(T,x) //從表格T刪除一個數(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ù)雜度用聚集法或計帳法難有直觀的結(jié)果。我們用勢能法。(接下頁)29平攤分析n次插入和刪除的操作的復(fù)雜度(繼續(xù))我們設(shè)計如下的勢能函數(shù)：當(dāng)Loading-factor(T)

0.5時，

(T)=2

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

(T)=0.5

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

(T0)=0。又因為，當(dāng)Loading-factor(T)

0.5時，

(T)=2

number(T)-size(T)

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

(T)=0.5

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

所以

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

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

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

0.5。這時，表格也許會擴張，因為插入前和插入后所用勢能函數(shù)都是

(T)=2

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

ai

=3。A.2

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

那么因為

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

=ci

+

(Ti)-

(Ti-1)=ci

+[0.5

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

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

=0(接下頁)31A.2 在插入時，Loading-factor(Ti-1)<0.5。(繼續(xù))如果插入后Loading-factor(Ti)=0.5，那么因為

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

//因為number(Ti-1)+1=0.5size(Ti-1) B. 第

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

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

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

0.5。(接下頁)32第

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

在刪除時，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(接下頁)33第

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

)B.2

在刪除時，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)以上說明，不論第

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

0.5時，

(Tn)=2

number(Tn)-size(Tn)

number(Tn)

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

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

最小二叉堆和最小斐波那契堆對基本操作的復(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個操作稱為可合并堆的操作。37斐波那契堆的結(jié)構(gòu)斐波那契堆H中的每一個結(jié)點x存有一個數(shù)據(jù)。它有以下屬性：

x.key

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

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

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

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

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

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

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

(H)=4+2

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

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

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

0x.p

nilx.child

nilx.mark

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

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

H

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

H.min //z指向最小點ifz

nil

then

for

eachchildxofz

addxtotherootlistofH //把x插入樹根表

x.p

nil

endfor

removezfromtherootlistofH

//摘除最小點

if

z=z.right

//原樹根表只有最小點

then

H.min

nil

else

H.min

z.right

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

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

endif

H.n

H.n-1

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

z

else

return

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

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

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

這個簡單的操作用子程序Fib-Heap-Link(H,y,x)來實現(xiàn)。

(接下頁)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)。該子程序通過一系列Fib-Heap-Link的合并操作使樹根表中每個樹根的度都不同。我們先建一個數(shù)組A[0..D]，其中A[k](0

k

D)，是用來指向度為k的樹根的指針，D

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

k

D)。然后，逐個檢查樹根表中的樹根。(接下頁)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)。顯然，這個合并的次數(shù)不會超過D=O(lgn)次。完成上述對樹根的合并后，子程序Consolidate(H)把數(shù)組A[0..D]中非空指針?biāo)赶虻臉涓橐粋€新的樹根表，并找出新的最小點。這時，子程序Consolidate(H)就完成了，摘取堆中最小點的操作Fib-Heap-Extract-Min(H)也隨之完成。下面是Consolidate(H)的偽碼。(接下頁)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

(接下頁)51Consolidate

(繼續(xù))

H.min

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

i

0to

D

ifA[i]

nil

then

ifH.min=nil //插入第一個樹根

thencreatearootlistforHcontainingjustA[i]

H.min

A[i]

elseinsertA[i]intoH’srootlist

if

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

thenH.min

A[i]

endif

endif

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

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

(a)

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

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

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

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

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

t(H)

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

置為新的值k，即x.key

k。如果點x是一個樹根，或者x.key

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

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

y為根的樹從

y的父親

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

x的關(guān)鍵字大于等于父親的關(guān)鍵字；第2步及以后每步是保證每個點最多被切去一個兒子，除非它在樹根環(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的長子

then

ifx.right≠x

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

then

y.child

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

else

y.child

nil

endifendifaddxtotherootlistofH

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

x.p

nilx.mark

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

(繼續(xù))z

y.pifz

nil

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

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

then

y.mark

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

else

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

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