二項(xiàng)堆和fibonacci堆的分析與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)論文-在線瀏覽
2024-07-29 06:35本頁(yè)面
【正文】 nion(H)1 H = Bin_Make()2 = Bin_Merge(H1,H2)3 free objects H1 and H2 but not the lists they point to4 if == NIL5 return H6 prev_x = NIL7 x = 8 next_x = 9 while next_x != NIL10 if ( != ) or ( != NIL and == )11 prev_x = x, x = next12 else if = 13 = 14 Bin_Link(next_x, x)15 else if prev_x == NIL16 = next_x17 else18 = next_x19 Bin_Link(x, next_x)20 x = next_x21 next_x = 22 return H 插入創(chuàng)建一個(gè)只包含要插入關(guān)鍵字的堆，再將此堆與原先的二項(xiàng)堆進(jìn)行合并，即可得到插入后的堆。偽代碼如下：Bin_Insert(H，x)1 subH = Bin_Make()2 = = = = = NIL3 H = Bin_Union(H, subH) 查找最小關(guān)鍵字由于滿足最小堆性質(zhì)，只需對(duì)二項(xiàng)堆的主鏈進(jìn)行一遍遍歷即可，因?yàn)閚個(gè)節(jié)點(diǎn)的二項(xiàng)堆的主鏈長(zhǎng)度不超過(guò)logn+1，所以查找最小關(guān)鍵字操作的時(shí)間復(fù)雜度為。由于每棵樹最多有l(wèi)ogn+1棵子樹，創(chuàng)建新堆的時(shí)間為。偽代碼如下：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ì)。重復(fù)上述操作直到該節(jié)點(diǎn)為根節(jié)點(diǎn)或者該節(jié)點(diǎn)的關(guān)鍵值小于其父節(jié)點(diǎn)的關(guān)鍵字及最小堆性質(zhì)得到滿足。偽代碼如下：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ù)無(wú)窮大（比二項(xiàng)堆中的其他所有關(guān)鍵字的值都小即可），再刪除最小關(guān)鍵字的結(jié)點(diǎn)即可。斐波那契堆不涉及刪除元素的操作有O(1)的平攤時(shí)間，因此如果程序中Decrease和Delete操作較少則能夠獲得極高效率。 斐波納契堆的特點(diǎn)與二項(xiàng)堆相似,斐波那契堆也是一種可合并堆，是由一組堆有序樹Decrease和構(gòu)成的集合。可是如果存在Decrease和Delete操作時(shí)必然會(huì)破壞二項(xiàng)圖的結(jié)構(gòu)。與二項(xiàng)堆不同的是主鏈上的堆有序樹不必按照度數(shù)大小從小到大排列。 斐波那契堆中每個(gè)節(jié)點(diǎn)的屬性包括：。對(duì)于一個(gè)特定的斐波那契堆，我們構(gòu)造一個(gè)數(shù)據(jù)結(jié)構(gòu)H。 斐波納契堆操作 斐波那契堆支持所有的堆操作，對(duì)于不涉及Delete的操作有O(1)的均攤運(yùn)行時(shí)間，其關(guān)鍵思想是將主鏈上的根節(jié)點(diǎn)的合并操作盡可能退后，來(lái)達(dá)到提高時(shí)間效率的目的。 插入一個(gè)結(jié)點(diǎn) 首先分配并且初始化一個(gè)節(jié)點(diǎn)x然后加入H的根表中。 = 0, = NIL, = NIL, = x, = x, ←=FALSE2 if = =NIL or 4 = + 1 下圖將關(guān)鍵字為21的結(jié)點(diǎn)插入斐波那契堆的示意圖。偽代碼如下：Fib_Union(H1, H2)1 = 3 if ( == NIL) or ( != NIL and )5 = + 7首先將最小節(jié)點(diǎn)的所有子節(jié)點(diǎn)與根表合并，然后刪除最小節(jié)點(diǎn)。偽代碼如下：Fib_Pop(H)1 if z !=NIL3 for each child x of z4 = – 11279行處理邊界情況，=。Consolidate函數(shù)調(diào)用之前程序執(zhí)行過(guò)程如下圖(a)~(b)。偽代碼如下：Consolidate(H)1 for i = 0 to D()2 x = w,d = 6 while A[d] != NIL7 y = A[d] if 9 exchange x ? y10 A[d] = NIL12 do if A[i] ≠ NIL17 remove y from the root list of H2A[i]中存放著對(duì)應(yīng)度數(shù)為i的二叉樹根節(jié)點(diǎn)。while循環(huán)反復(fù)講相同度數(shù)的二叉樹進(jìn)行連接操作。 減小一個(gè)關(guān)鍵字 斐波那契堆利用級(jí)聯(lián)剪枝的技術(shù)來(lái)維護(hù)斐波那契的性質(zhì)。偽代碼如下：1 = k4 if y != NIL and 6 if 9 = xCUT(H, x, y)1 remove x from the child list of y, decrementing degree[y]2 add x to the root list of H3 = NIL4 = FALSECASCADINGCUT(H, y)1 z = 2 if z != NIL3 =TRUE5 else CUT(H, y, z)6 CASCADINGCUT(H, z)下圖中：(a),(b)46減小為5； 級(jí)聯(lián)剪切的過(guò)程如下：， = = ， == true，操作結(jié)束。如果不進(jìn)行級(jí)聯(lián)剪枝操作的話，我們可以發(fā)現(xiàn)刪除幾個(gè)節(jié)點(diǎn)后樹的形狀就會(huì)顯得十分凌亂毫無(wú)章法。由于二項(xiàng)式是對(duì)稱的，因此通過(guò)級(jí)聯(lián)減枝的技術(shù)可以保證類使二項(xiàng)式減少一個(gè)數(shù)量級(jí)，維持二項(xiàng)樹的形狀。偽代碼如下：Fib_Delete(H, x)1 Fib_Decrease (H, x, ∞)2 Fib_Pop (H)第5章 實(shí)現(xiàn)細(xì)節(jié) 二項(xiàng)堆涉及到的數(shù)據(jù)結(jié)構(gòu)主要包括bin_node 和 bin_heap，具體定義如下：struct bin_node { struct bin_node *father。 struct bin_node *rsibling。 int degree。struct bin_heap { struct bin_node *head。}。bin_link(),此函數(shù)接受兩個(gè)bin_node結(jié)構(gòu)體指針作為參數(shù)，將對(duì)應(yīng)的兩棵二項(xiàng)樹合并并且返回結(jié)果樹的根節(jié)點(diǎn)指針。bin_Union(),此函數(shù)接受兩個(gè)bin_heap結(jié)構(gòu)體指針作為參數(shù)，內(nèi)部調(diào)用bin_merge()合并主鏈，然后對(duì)主鏈上相
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1