【導(dǎo)讀】堆是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常被視為部分有序的樹。堆總是滿足堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值這個(gè)。通常將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最。常見(jiàn)的堆的實(shí)現(xiàn)包括二叉堆、二項(xiàng)堆，斐波那契堆。法中發(fā)揮重要作用。斐波那契堆有著非常好的均攤運(yùn)行時(shí)間，可是其數(shù)據(jù)結(jié)構(gòu)和。間，同時(shí)數(shù)據(jù)結(jié)構(gòu)相對(duì)比較簡(jiǎn)潔的實(shí)現(xiàn)算法。本課題的目的是學(xué)習(xí)連續(xù)空間上二。通過(guò)具體代碼實(shí)現(xiàn)來(lái)對(duì)比二項(xiàng)堆和斐波那契堆實(shí)現(xiàn)

　　

【正文】 _heap 的結(jié)構(gòu)體并且初始化，函數(shù)返回對(duì)應(yīng)結(jié)構(gòu)體的指針。 fib_link(),此函數(shù)接受兩個(gè) fib_node 結(jié)構(gòu)體指針，將兩個(gè)無(wú)序的二項(xiàng)樹合并，并且返回對(duì)應(yīng)結(jié)果樹的根節(jié)點(diǎn)。 fib_replace(),此函數(shù)改變某個(gè)節(jié)點(diǎn)的關(guān)鍵值，同時(shí)經(jīng)過(guò)級(jí)聯(lián)剪切的操作的維護(hù)斐波那契堆的數(shù)學(xué)性質(zhì)和結(jié)構(gòu)。 fib_Union(),此函數(shù)接受兩個(gè) fib_heap 結(jié)構(gòu)體指針，將對(duì)應(yīng)的斐波納契堆合并，返回合并后的堆的根節(jié)點(diǎn)。 _listsize(),此函數(shù)接受一個(gè) fib_heap 結(jié) 構(gòu)體指針， 通過(guò)遍歷根鏈得到根鏈長(zhǎng)度的最大度數(shù)，通過(guò)這些 計(jì)算要用到的臨時(shí)數(shù)組的大小 。 consolidate(),此函數(shù)實(shí)現(xiàn)級(jí)聯(lián)剪切的操作。 fib_Push(), fib_Pop(), fib_Top()實(shí)現(xiàn)對(duì)斐波那契堆的基本操作進(jìn)行封裝，提供抽象的接口。 fib_func_test（） ,斐波納契堆的測(cè)試函數(shù)，不包括性能測(cè)試，主要是對(duì) Push,Pop和 Top 操作進(jìn)行測(cè)試。 其他函數(shù) 21 代碼還涉及到的其他函數(shù) ： 比較函數(shù)：實(shí)現(xiàn) 的操作。在二項(xiàng)堆中為 le()，在斐波納契堆為 _le()。 遍歷函數(shù)： 用于對(duì)根鏈進(jìn)行遍歷，同時(shí)格式化輸出根鏈上的節(jié)點(diǎn)的關(guān)鍵字值和度數(shù)。在二項(xiàng)堆中為 repr()，在斐波那契堆中為 _repr()。 報(bào)錯(cuò)函數(shù)：通過(guò) stdout 的重定位，將內(nèi)存不足的情況寫入 stdout 的緩沖區(qū)，同時(shí)進(jìn)行 flush 操作。在代碼中為 raise()。 性能測(cè)試函數(shù)：通過(guò)對(duì) 100000 個(gè)隨機(jī)數(shù)進(jìn)行 Push 和 Pop 操作，計(jì)算出兩種操作所耗費(fèi)的掛鐘時(shí)間。重復(fù)這個(gè)這個(gè)操作多遍，取平均值。在代碼中實(shí)現(xiàn)為profiler()。 福州大學(xué)本科生畢業(yè)設(shè)計(jì) (論文 ) 22 第 6 章 性能測(cè)試 我們對(duì)二項(xiàng)堆和斐波那契堆的 Push 和 Pop 操作進(jìn)行測(cè)試。 我們先利用 rand()函數(shù)生成 大量的 隨機(jī)數(shù)，然后對(duì)數(shù)據(jù)進(jìn)行 Push 和 Pop 操作，并且利用 clock()函數(shù) 來(lái)測(cè)試相應(yīng)操作的掛鐘時(shí)間，并將結(jié)果用 CLOCK_PER_SEC 去除得到最后的時(shí)間。重復(fù)這樣的測(cè)試多次取 平均值。 在具體代碼中對(duì)應(yīng)的測(cè)試函數(shù)為 profiler()。它有 2 個(gè)參數(shù)，分別是 t 即實(shí)驗(yàn)重復(fù)次數(shù)， mode 即表明是對(duì)二項(xiàng)堆還是對(duì)斐波那契堆進(jìn)行測(cè)試，或者以比較模式進(jìn)行測(cè)試。全局變量 SIZE_FOR_TEST 為測(cè)試數(shù)據(jù)規(guī)模。 通過(guò) 對(duì) 100000 個(gè)數(shù) 據(jù)進(jìn)行測(cè)試 的實(shí)驗(yàn) ， 我們 得到下列結(jié)果 。 Binomial size: 100000 clocks clocks sds sds all 31 156 32 156 31 140 31 141 31 140 Fibonacci size: 100000 clocks clocks sds sds all 15 94 15 94 31 78 31 94 16 93 Compare size: 100000 format: b f clocks clocks sds sds all 46 156 23 16 94 31 172 15 94 31 172 15 94 31 140 31 94 31 140 16 78 上面 的數(shù)據(jù)對(duì)于的是對(duì)二項(xiàng)堆（ Binomial），斐波納契堆（ Fibonacci）和在比較模式下通過(guò)對(duì) 100000 數(shù)據(jù)進(jìn)行 5 次重復(fù)測(cè)試的結(jié)果。其中 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í)間。 福州大學(xué)本科生畢業(yè)設(shè)計(jì) (論文 ) 24 總結(jié)與展望 數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)是一門創(chuàng)造性的學(xué)問(wèn)，需要良好的數(shù)學(xué)背景和清晰的邏輯思維同時(shí)對(duì)抽象現(xiàn)實(shí)問(wèn)題的能力提出很高的要求。 面對(duì)日益增加的數(shù)據(jù)處理規(guī)模，常規(guī)的數(shù)據(jù)結(jié)構(gòu)和算法無(wú)法滿足運(yùn)行時(shí)間的要求。因此精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)算法成為解決問(wè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ì)。 堆作為一種應(yīng)用 廣泛的數(shù)據(jù)結(jié)構(gòu)，得到許多人研究。人們不停的在探索這種抽象數(shù)據(jù)結(jié)構(gòu)更好的實(shí)現(xiàn)算法。本文在認(rèn)真學(xué)習(xí)二項(xiàng)堆與斐波那契堆的數(shù)據(jù)結(jié)構(gòu)，數(shù)學(xué)性質(zhì)和實(shí)現(xiàn)算法的基礎(chǔ)上給出了具體的代碼實(shí)現(xiàn)并且對(duì)效率進(jìn)行了分析。二項(xiàng)堆解決了離散空間上面堆的實(shí)現(xiàn)問(wèn)題，與二叉堆有相同的漸近時(shí)間復(fù)雜度。斐波納契堆在不涉及刪除操作的情況下有 O(1)的均攤時(shí)間復(fù)雜度，無(wú)疑是對(duì)效率的極大提升。但是相對(duì)而言斐波納契堆有著復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法是其主要的不足。 如果能夠開發(fā)一種堆的算法，既有比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)有能高效支持對(duì)應(yīng)的操作是再好不過(guò)的事情了。而這也是 我們要努力的目標(biāo)。 25 致 謝 首先，我要誠(chéng)摯地感謝我的導(dǎo)師陳歡老師！本論文是在陳歡老師的悉心指導(dǎo)下完成的，從論文的構(gòu)思、準(zhǔn)備、編寫到最后的定稿，都得到了陳歡老師的大力支持和熱心指導(dǎo)。在論文的編寫過(guò)程中，陳歡老師提出了許多的寶貴意見(jiàn)和建議，使我得到了很大的啟發(fā)。在此，我要向陳歡老師致以衷心的感謝！ 同時(shí)我也要感謝我的一些同學(xué)和朋友，他們?cè)谖易霎呍O(shè)的過(guò)程之中給我許多幫助，同他們討論問(wèn)題使我受益匪淺。 最后，感謝各位評(píng)審老師在百忙之中抽出寶貴的時(shí)間對(duì)本論文進(jìn)行審閱和參加答辯。在此， 對(duì)各位參加審閱和答辯的老師表示感謝！ 福州大學(xué)本科生畢業(yè)設(shè)計(jì) (論文 ) 26 參考文獻(xiàn) [1] Tomas , Charles E. Leiserson Ronald L. Rivest《算法導(dǎo)論》第二版，機(jī)械工業(yè)出版社。 [2] Jon Bentley 《編程珠璣》第三版，人民郵電出版社。 [3] Mark Allen Weiss 《 Data Structures and Algorithm Analysis in C》第二版機(jī)械工業(yè)出版社。 [4] 嚴(yán)蔚敏 吳偉民 《數(shù)據(jù)結(jié)構(gòu)》 清華大學(xué)出版社 。 [5]Sartaj Sahni 《數(shù)據(jù)結(jié)構(gòu)，算法與應(yīng)用》 機(jī)械工業(yè)出版社。 27