二項(xiàng)堆和fibonacci堆的分析與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)論文(編輯修改稿)
2024-07-15 06:35 本頁面
【文章內(nèi)容簡介】 logn+1棵子樹，創(chuàng)建新堆的時(shí)間為。同時(shí)合并堆的時(shí)間也為，故整個(gè)操作的時(shí)間復(fù)雜度為。偽代碼如下：Bin_Pop(H)1 find the node with smallest key value on main chain and remove it from main chain.2 subH = Bin_Make()3 reverse the order of the linked list of x’s children, set the p field of each child to NIL and set head[H] to the the head of the resulting list.4 H = Bin_Union(H, subH)5 return x 減小關(guān)鍵字的值由于在減小關(guān)鍵字的值后，可能不再滿足最小堆性質(zhì)。此時(shí)，將其所在結(jié)點(diǎn)與父結(jié)點(diǎn)交換關(guān)鍵字同時(shí)將指針指向父節(jié)點(diǎn)。重復(fù)上述操作直到該節(jié)點(diǎn)為根節(jié)點(diǎn)或者該節(jié)點(diǎn)的關(guān)鍵值小于其父節(jié)點(diǎn)的關(guān)鍵字及最小堆性質(zhì)得到滿足。操作的時(shí)間復(fù)雜度為。偽代碼如下：Bin_Decrease(H，x, k)1 = k ,y = x, z = 2 while z !=NIL and 3 swamp and 4 y = z, z = 刪除將需要?jiǎng)h除的結(jié)點(diǎn)的關(guān)鍵字的值減小到負(fù)無窮大（比二項(xiàng)堆中的其他所有關(guān)鍵字的值都小即可），再刪除最小關(guān)鍵字的結(jié)點(diǎn)即可。偽代碼如下：Bin_Delete(H, x)1 Bin_Decrease(H, x, infinite)2 Bin_Pop(H)第4章 斐波那契堆斐波那契堆是計(jì)算計(jì)科學(xué)中中最小堆有序樹的集合，它和二項(xiàng)堆有類似的性質(zhì)。斐波那契堆不涉及刪除元素的操作有O(1)的平攤時(shí)間，因此如果程序中Decrease和Delete操作較少則能夠獲得極高效率。，。同時(shí)x的所有子節(jié)點(diǎn)都用雙向循環(huán)鏈表鏈接起來。 斐波納契堆的特點(diǎn)與二項(xiàng)堆相似,斐波那契堆也是一種可合并堆，是由一組堆有序樹Decrease和構(gòu)成的集合。如果不對(duì)斐波納契堆進(jìn)行Decrease和Delete操作那么集合中的樹都是二叉樹。可是如果存在Decrease和Delete操作時(shí)必然會(huì)破壞二項(xiàng)圖的結(jié)構(gòu)。在這種情況下會(huì)出現(xiàn)樹高為k，結(jié)點(diǎn)個(gè)數(shù)少于2k的情況。與二項(xiàng)堆不同的是主鏈上的堆有序樹不必按照度數(shù)大小從小到大排列。 上圖是斐波那契堆的示意圖。 斐波那契堆中每個(gè)節(jié)點(diǎn)的屬性包括：，，。其中任意節(jié)點(diǎn)的所有子女被組織成循環(huán)雙向鏈表。對(duì)于一個(gè)特定的斐波那契堆，我們構(gòu)造一個(gè)數(shù)據(jù)結(jié)構(gòu)H。在斐波那契堆中，所有樹的根節(jié)點(diǎn)都鏈接成一個(gè)環(huán)形的雙鏈表，稱為堆的根表。 斐波納契堆操作 斐波那契堆支持所有的堆操作，對(duì)于不涉及Delete的操作有O(1)的均攤運(yùn)行時(shí)間，其關(guān)鍵思想是將主鏈上的根節(jié)點(diǎn)的合并操作盡可能退后，來達(dá)到提高時(shí)間效率的目的。 創(chuàng)建一個(gè)新的斐波那契堆過程Fib_Make() 分配并初始化一個(gè)斐波那契堆對(duì)象H。 插入一個(gè)結(jié)點(diǎn) 首先分配并且初始化一個(gè)節(jié)點(diǎn)x然后加入H的根表中。偽代碼如下：Fib_Insert(H, x)1 = 0, = NIL, = NIL, = x, = x, ←=FALSE2 merge the root list which contains x to root list H3 if = =NIL or 4 = x5 = + 1 下圖將關(guān)鍵字為21的結(jié)點(diǎn)插入斐波那契堆的示意圖。 合并兩個(gè)斐波那契堆由于雙向鏈表的數(shù)據(jù)結(jié)構(gòu)同時(shí)根表上的節(jié)點(diǎn)度數(shù)無序的性質(zhì)，因此只需把兩個(gè)根表連接同時(shí)比較最小關(guān)鍵節(jié)點(diǎn)取其中較小的即可。偽代碼如下：Fib_Union(H1, H2)1 H = Fib_Make()2 = 3 merge the root list of H2 with the root list of H4 if ( == NIL) or ( != NIL and )5 = 6 = + 7 free H1 and H2 return H 抽取最小結(jié)點(diǎn)抽取最小節(jié)點(diǎn)是比較復(fù)雜的操作。首先將最小節(jié)點(diǎn)的所有子節(jié)點(diǎn)與根表合并，然后刪除最小節(jié)點(diǎn)。最后調(diào)用輔助過程CONSOLIDATE對(duì)根表上度數(shù)相同的根節(jié)點(diǎn)進(jìn)行合并。偽代碼如下：Fib_Pop(H)1 z = 2 if z !=NIL3 for each child x of z4 add x to the root list of H5 = NIL6 remove z from the root list of H7 if z = 8 = NIL9else = 10Consolidate (H)11 = – 112 return z Fib_Pop中，3~5行把z的子節(jié)點(diǎn)合并到根表上去，第6行將z節(jié)點(diǎn)從根表中去掉。79行處理邊界情況，，=。注意這里 。Consolidate函數(shù)調(diào)用之前程序執(zhí)行過程如下圖(a)~(b)。 Consolidate過程要做的工作是通過遍歷一遍根鏈?zhǔn)沟糜邢嗤葦?shù)的根節(jié)點(diǎn)合并，最終使得根鏈上不存在度數(shù)相同的根節(jié)點(diǎn)。偽代碼如下：Consolidate(H)1 for i = 0 to D()2 A[i] = NIL3 for each node w in the root list of H4 x = w,d = 6 while A[d] != NIL7 y = A[d] 8 if 9 exchange x ? y10 Fib_Link(H, y, x)11 A[d] = NIL121
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1