【文章內(nèi)容簡介】 二項堆是指滿足以下性質的二項樹的集合： (1)每棵二項樹都滿足堆性質，即任意結點關鍵字大于等于其父結點的關鍵字。 (2)集合中 不能有兩棵或者兩棵以上的二項樹有相同度數(shù)。 上圖是 含 13 個結點的二項堆 示意圖。 由于 我們并不 需要對二項樹的根結點 9 進行 隨機存取 的操作 ， 我們將這些根節(jié)點按照度數(shù)從小到大的次序鏈接成一條單鏈 ，形成的鏈表我們稱為主鏈。 因此 以上第一個性質保證了二項樹的 主鏈 包含了最小的關鍵字。以上第二個性質則說明結點數(shù)為 n 的二項堆 的根鏈上至多 有棵二項樹。 對于二叉堆中的每個節(jié)點 x 包括以 下屬性：子女個數(shù)，最左孩子 ，右兄弟 ，父節(jié)點 ， 關鍵字 。對于一個抽象的二項堆 H， 表示主鏈首部， 表示堆中節(jié)點的個數(shù)。 二項堆的操作 合并 上圖是兩棵二項樹合并的示意圖。 上圖是兩個二叉堆合并的示意圖。 最基本的為二個度數(shù)相同的二項樹的合并。由于二項樹根結點包含最小的關鍵字，因此在二顆樹合并時，只需比較二個根結點關鍵字的大小，其中含小關鍵字的結點成為結果樹的根結點，另一棵樹則變成結果樹的 最左孩子 。 偽代碼如下： Bin_Link(y, z) 1 ← z 2 ← 3 ← y 4 ← +1 福州大學本科生畢業(yè)設計 (論文 ) 10 上圖是如何遍歷主鏈的示意圖。 兩個二項堆的合并可按如下步驟進行： 因為主鏈上的根節(jié)點的 度數(shù) i 從小到大排列且不存在兩個相同度數(shù)的根節(jié)點在同一主鏈上，因此可以對兩個主鏈按照根節(jié)點的度數(shù)從小到大進行遍歷合并得到一條主鏈。在得到的這條主鏈上度數(shù)為i 的根節(jié)點至多有兩個且相鄰。因此我們對主鏈進行一次遍歷，在遍歷過程中 度數(shù)為 i的根節(jié)點只可能有 1 個， 2 個或者 3 個。我們利用三個指針 prev_x， x， next_x來遍歷主鏈。來如果當前度數(shù)為 i的根結只有一個或者三個則指針指向下一個節(jié)點，如果只有兩個則合并兩棵二叉樹并且將新的根節(jié)點加入主鏈。由于含有 n個節(jié)點的二叉堆的主鏈長度不超過 logn+1，并且我們只遍歷了兩遍主鏈，因此合并 操作的時間復雜度為 。 偽代碼如下 : Bin_Union(H) 1 H = Bin_Make() 2 = Bin_Merge(H1,H2) 3 free objects H1 and H2 but not the lists they point to 4 if == NIL 5 return H 6 prev_x = NIL 7 x = 8 next_x = 9 while next_x != NIL 10 if ( != ) or ( != NIL and == ) 11 prev_x = x, x = next 12 else if = 13 = 14 Bin_Link(next_x, x) 15 else if prev_x == NIL 16 = next_x 17 else 18 = next_x 19 Bin_Link(x, next_x) 20 x = next_x 21 next_x = 11 22 return H 插入 創(chuàng)建一個只包含要插入關鍵字的堆，再將此堆與原先的二項堆進行合并，即可得到插入后的堆。由于需要合并 操作的時間復雜度為 ， 因此 插入操作 的時間復雜度為 。 偽代碼如下： Bin_Insert(H， x) 1 subH = Bin_Make() 2 = = = = = NIL 3 H = Bin_Union(H, subH) 查找最小關鍵字 由于滿足最小堆性質，只需 對二項堆的主鏈進行一遍遍歷 即可， 因為 n 個節(jié)點的二項堆的主鏈長度不超過 logn+1，所以查找 最小關鍵字操作的時間復雜度為。 偽代碼如下： Bin_Top (H) 1 y = NIL 2 x = 3 min = infinite 4 while x != NIL 5 if min 6 min = 7 y = x 8 x = 9 return y 刪除最小關鍵字 首先 先找到最小關鍵字所在結點，將 該節(jié)點的 子樹看作一個獨立的二項堆，再將此堆合并到原先的堆中 ，然后刪除最小關鍵節(jié)點 即可。由于每棵樹最多有l(wèi)ogn+1 棵子樹，創(chuàng)建新堆的時間為 。同時合并堆的時間也為 ，故整個操作 的時間復雜度 為 。偽代碼如下： 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 福州大學本科生畢業(yè)設計 (論文 ) 12 減小關鍵字的值 由于 在減小關鍵字的值后，可能不 再 滿足最小堆性質。此時，將其所在結點與父結點交換關鍵字 同時將指針指向父節(jié)點。重復上述操作直到該節(jié)點為根節(jié)點或者該節(jié)點的關鍵值小于其父節(jié)點的關鍵字及 最小堆性質得到滿足。操作 的時間復雜度 為 。 偽代碼如下： Bin_Decrease(H， x, k) 1 = k ,y = x, z = 2 while z !=NIL and 3 swamp and 4 y = z, z = 刪除 將需要刪除的結點的關鍵字的值減小到負無窮大（比二項堆中的其他所有關鍵字的值都小即可），再刪除最小關鍵字的結點即可。 偽代碼如下： Bin_Delete(H, x) 1 Bin_Decrease(H, x, infinite) 2 Bin_Pop(H) 13 第 4 章 斐波那契堆 斐波納契堆定義 斐波那契堆是計 算計科學中 中最小堆有 序樹 的集合 ， 它和 二項堆 有類似的性質 。斐波那契堆 不涉及刪除元素的操作有 O(1)的平攤時間 ，因此如果程序中Decrease 和 Delete 操作較少則能夠獲得極高 效率 。斐波那契堆中 每個節(jié)點 x 包含指向父節(jié)點的指針 ， 指向任意一個子結點的 ，表示 x 的節(jié)點個數(shù)， 指向它的左兄弟的 和右兄弟的 。 同時 x 的所有子節(jié)點都用雙向循環(huán)鏈表鏈接起來 。 斐波納契堆的 特點 與二項堆相似 ,斐波那契堆 也是一種可合并堆 ，是 由一組 堆有序 樹 Decrease 和構 成的集合 。 如果不對斐波納契堆進行 Decrease 和 Delete 操作那么集合中的樹都是二叉樹?？墒侨绻嬖?Decrease 和 Delete 操作時必然會破壞二項圖的結構。在這種情況下會出現(xiàn) 樹高為 k，結點個數(shù)少于 2k 的情況 。 與二項堆不同的是主鏈上的堆有序樹不必按照度數(shù)大小從小到大排列。 上圖是斐波那契堆的示意圖。 斐波那契堆中每個節(jié)點的屬性包括： 父節(jié)點 ， 指向任一子女的指針， 左兄弟 ， 右兄弟 ， 子女的個數(shù) ， 布爾值域 。其中任意節(jié)點的所有子女被組織成循環(huán)雙向鏈表， 表示節(jié)點 x 成為另一個節(jié)點的 子節(jié)點以來是否失去了一個孩子。 對于一個 特 定的斐波那契堆 ，我們構造一個數(shù)據(jù)結構 H， 其中 表示堆的大小， 指向堆中最小節(jié)點。 在斐波福州大學本科生畢業(yè)設計 (論文 ) 14 那契堆中，所有樹的根 節(jié)點 都鏈接成一個環(huán)形的雙鏈表，稱為堆的 根表 。 斐波納契堆操作 斐波那契堆支持所有的堆操作，對于不涉及 Delete 的操作有 O(1)的均攤運行時間，其關鍵思想是將主鏈上的根節(jié)點的合并操作盡可能退后，來達到提高時間效率的目的。 創(chuàng)建一個新的斐波那契堆 過程 Fib_Make() 分配并 初始化一個 斐波那契堆對象 H。 插入一個結點 首先分配并且初始化一個節(jié)點 x 然后 加入 H 的根表中。偽代碼 如下 ： Fib_Insert(H, x) 1 = 0, = NIL, = NIL, = x, = x, ← =FALSE 2 merge the root list which contains x to root list H 3 if = =NIL or 4 = x 5 = + 1 下 圖將關鍵字為 21 的結點插入斐波那契堆 的示意圖 。 合并兩個斐波那契堆 由于雙向鏈表的數(shù)據(jù)結構同時根表上的節(jié)點度數(shù)無序的性質，因此只需把兩個根表連接同時比較最小關鍵節(jié)點取其中較小的即可。 偽代碼 如下 ： Fib_Union(H1, H2) 1 H = Fib_Make() 2 = 3 merge the root list of H2 with the root list of H 4 if (