【正文】
27。[4] 嚴(yán)蔚敏 吳偉民 《數(shù)據(jù)結(jié)構(gòu)》 清華大學(xué)出版社。[2] Jon Bentley 《編程珠璣》第三版,人民郵電出版社。 最后,感謝各位評(píng)審老師在百忙之中抽出寶貴的時(shí)間對(duì)本論文進(jìn)行審閱和參加答辯。在論文的編寫(xiě)過(guò)程中,陳歡老師提出了許多的寶貴意見(jiàn)和建議,使我得到了很大的啟發(fā)。而這也是我們要努力的目標(biāo)。但是相對(duì)而言斐波納契堆有著復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法是其主要的不足。二項(xiàng)堆解決了離散空間上面堆的實(shí)現(xiàn)問(wèn)題,與二叉堆有相同的漸近時(shí)間復(fù)雜度。人們不停的在探索這種抽象數(shù)據(jù)結(jié)構(gòu)更好的實(shí)現(xiàn)算法。從計(jì)算機(jī)科學(xué)誕生伊始,數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)也隨之產(chǎn)生,一代一代的計(jì)算機(jī)科學(xué)家,工程師為了解決問(wèn)題提出了許許多多的精巧的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。面對(duì)日益增加的數(shù)據(jù)處理規(guī)模,常規(guī)的數(shù)據(jù)結(jié)構(gòu)和算法無(wú)法滿足運(yùn)行時(shí)間的要求。其中clocks代表push操作耗費(fèi)的掛鐘時(shí)間,clocks代表pop操作耗費(fèi)的掛鐘時(shí)間, sds代表push操作耗費(fèi)了幾秒, sds代表pop操作耗費(fèi)了幾秒, all代表一次實(shí)驗(yàn)總共耗費(fèi)的時(shí)間。通過(guò)對(duì)100000個(gè)數(shù)據(jù)進(jìn)行測(cè)試的實(shí)驗(yàn),我們得到下列結(jié)果。它有2個(gè)參數(shù),分別是t即實(shí)驗(yàn)重復(fù)次數(shù),mode即表明是對(duì)二項(xiàng)堆還是對(duì)斐波那契堆進(jìn)行測(cè)試,或者以比較模式進(jìn)行測(cè)試。重復(fù)這樣的測(cè)試多次取平均值。第6章 性能測(cè)試我們對(duì)二項(xiàng)堆和斐波那契堆的Push和Pop操作進(jìn)行測(cè)試。重復(fù)這個(gè)這個(gè)操作多遍,取平均值。在代碼中為raise()。在二項(xiàng)堆中為repr(),在斐波那契堆中為_(kāi)repr()。在二項(xiàng)堆中為le(),在斐波納契堆為_(kāi)le()。fib_func_test(),斐波納契堆的測(cè)試函數(shù),不包括性能測(cè)試,主要是對(duì)Push,Pop和Top操作進(jìn)行測(cè)試。consolidate(),此函數(shù)實(shí)現(xiàn)級(jí)聯(lián)剪切的操作。fib_Union(),此函數(shù)接受兩個(gè)fib_heap結(jié)構(gòu)體指針,將對(duì)應(yīng)的斐波納契堆合并,返回合并后的堆的根節(jié)點(diǎn)。fib_link(),此函數(shù)接受兩個(gè)fib_node結(jié)構(gòu)體指針,將兩個(gè)無(wú)序的二項(xiàng)樹(shù)合并,并且返回對(duì)應(yīng)結(jié)果樹(shù)的根節(jié)點(diǎn)。}。struct fib_heap { struct fib_node *head。 void *data。 int mark。 struct fib_node *child。斐波那契堆涉及到的數(shù)據(jù)結(jié)構(gòu)主要包括fib_node 和 fib_heap,具體定義如下:struct fib_node { struct fib_node *left。bin_Push(),bin_Pop(),bin_Top(),這些函數(shù)對(duì)堆的基本操作進(jìn)行封裝,提供抽象的接口。bin_empty(),此函數(shù)返回一個(gè)布爾值來(lái)判定對(duì)應(yīng)的二項(xiàng)堆是否為空。bin_replace(),此函數(shù)改變某個(gè)節(jié)點(diǎn)的關(guān)鍵字值,并且通過(guò)遞歸的父節(jié)點(diǎn)比較關(guān)鍵字值來(lái)維持堆的有序結(jié)構(gòu)。bin_merge(),此函數(shù)接受兩個(gè)bin_heap結(jié)構(gòu)體指針作為參數(shù),將對(duì)應(yīng)的兩個(gè)二項(xiàng)堆的主鏈按序合并,并將結(jié)果主鏈的頭部指針?lè)祷亍?主要涉及到的函數(shù)如下:bin_Make(),此函數(shù)分配一個(gè)bin_heap結(jié)構(gòu)體指針并且初始化然后返回對(duì)應(yīng)的結(jié)構(gòu)體指針。 int size。}。 void *data。 struct bin_node *lchild。 刪除一個(gè)結(jié)點(diǎn)刪除操作的過(guò)程比較簡(jiǎn)單,, 然后調(diào)用彈出操作函數(shù)即可。但是如果進(jìn)行了級(jí)聯(lián)剪枝,在偶數(shù)個(gè)結(jié)點(diǎn)時(shí)進(jìn)行級(jí)聯(lián)剪切時(shí),原來(lái)是C(3, 0 )= 1, C(3, 1) = 3, C(3, 2) = 3, C(3, 3) = 1, 減少兩個(gè)結(jié)點(diǎn)關(guān)鍵字后,變?yōu)椋篊(2, 0) = 0,C(2, 1) = 2, C(2, 2) = 1。那么為什么偶數(shù)個(gè)的時(shí)候要遞歸往上刪除?因?yàn)槎葦?shù)為k的二項(xiàng)樹(shù)在i層共有C(k, i)個(gè)結(jié)點(diǎn)(i= 0, 1, 2, ……, k)。 (c),(d),(e)35減小為5 if = FALSE4 CASCADINGCUT(H, y)8 CUT(H, x, y)7 y = 5 error new key is greater than current key3 if k 2如果執(zhí)行Decrease操作的結(jié)點(diǎn)破壞了最小堆性質(zhì),則把該節(jié)點(diǎn)從其所在的雙向循環(huán)鏈表中剝離出來(lái)同時(shí)插入到根鏈中。14~19行根據(jù)數(shù) 組A重新構(gòu)造根表。其中3~13行保證每個(gè)度數(shù)要么沒(méi)有對(duì)應(yīng)二叉樹(shù)要么只有一棵二叉樹(shù)。 這個(gè)過(guò)程中用到數(shù)組A[]。 make y a child of x, incrementing 3 = FALSE if = NIL or A[i].key 19 = A[i]FibLink(H, y, x)1 add A[i] to the root list of H18 A[d] = x14 = NIL15 for i = 0 to D()16 d = d + 113 Fib_Link(H, y, x)11 8 A[i] = NIL3 for each node w in the root list of H4 Consolidate過(guò)程要做的工作是通過(guò)遍歷一遍根鏈?zhǔn)沟糜邢嗤葦?shù)的根節(jié)點(diǎn)合并,最終使得根鏈上不存在度數(shù)相同的根節(jié)點(diǎn)。注意這里 。 Fib_Pop中,3~5行把z的子節(jié)點(diǎn)合并到根表上去,第6行將z節(jié)點(diǎn)從根表中去掉。 return zConsolidate (H)11else = 10 = NIL9if z = 8remove z from the root list of H7 = NIL6 add x to the root list of H5 z = 2最后調(diào)用輔助過(guò)程CONSOLIDATE對(duì)根表上度數(shù)相同的根節(jié)點(diǎn)進(jìn)行合并。抽取最小節(jié)點(diǎn)是比較復(fù)雜的操作。 free H1 and H2 return H 抽取最小結(jié)點(diǎn) = 6 merge the root list of H2 with the root list of H4 H = Fib_Make()2 合并兩個(gè)斐波那契堆由于雙向鏈表的數(shù)據(jù)結(jié)構(gòu)同時(shí)根表上的節(jié)點(diǎn)度數(shù)無(wú)序的性質(zhì),因此只需把兩個(gè)根表連接同時(shí)比較最小關(guān)鍵節(jié)點(diǎn)取其中較小的即可。 = x5 merge the root list which contains x to root list H3偽代碼如下:Fib_Insert(H, x)1 創(chuàng)建一個(gè)新的斐波那契堆過(guò)程Fib_Make() 分配并初始化一個(gè)斐波那契堆對(duì)象H。在斐波那契堆中,所有樹(shù)的根節(jié)點(diǎn)都鏈接成一個(gè)環(huán)形的雙鏈表,稱為堆的根表。其中任意節(jié)點(diǎn)的所有子女被組織成循環(huán)雙向鏈表。 上圖是斐波那契堆的示意圖。在這種情況下會(huì)出現(xiàn)樹(shù)高為k,結(jié)點(diǎn)個(gè)數(shù)少于2k的情況。如果不對(duì)斐波納契堆進(jìn)行Decrease和Delete操作那么集合中的樹(shù)都是二叉樹(shù)。同時(shí)x的所有子節(jié)點(diǎn)都用雙向循環(huán)鏈表鏈接起來(lái)。偽代碼如下:Bin_Del