計算機科學外文翻譯-資料下載頁
2025-05-11 17:08本頁面
【導讀】1,k?2,...,2,1,0(inthisorder).atdepth.and0(seefigurebelow).
【正文】 樹的根節(jié)點，因此二叉樹的根節(jié)點可以按照對應階數(shù)的增序存儲在一個鏈表中。 合并 正如上面所提到的，最簡單的和最重要的操作是 在兩個二叉堆中 合并兩個 階數(shù)相同的 二叉樹。由于二叉樹的結構， 它們能夠被輕易的合并 。 由于二叉樹的根節(jié)點具有最小關鍵字，通過比較兩個根節(jié)點的關鍵字大小 ，其中較小的 成為最小關鍵字 ，并成為新的根節(jié)點。 另外一棵樹成為合并后的樹的一顆子樹 。 這個操作 對于合并兩個二項堆而言是基礎的。 function mergeTree(p, q) if = return (q) else return (p) 對應上圖，為了合并兩棵階數(shù)相同的二項樹 ，首先比較 根節(jié)點的關鍵字。因為7 3，在左邊的黑色樹（根節(jié)點 7）連接到灰樹（與根結點 3）右邊的子樹。結果是 棵 3 階樹。 合并兩個堆的操作也許是最有趣的，可以用來作為在大多數(shù)其他操作的子程序。和合并算法相似的是兩個二項堆 的根節(jié)點鏈表同時被遍歷。 如果只有一個堆包含 j 階的樹，這棵樹被移動到合并后的堆。如果兩個堆 都 包含j階的樹，兩棵樹被合并 成一顆滿足最小堆性質的階數(shù)為 j+1 的二叉樹 。 注意這棵樹以后也可能要和某個堆中 j+1 階的二叉樹合并 。在算法的過程中，我們需要研究最三棵樹 的 任何順序 的情況。 因為 二項堆中的每棵二項樹與表示二項堆大小的二進制表示中的一位對應 ， 合并兩個二項堆與兩個二進制數(shù)相加是相似的。由右至左，每當一個進位產生時都意味著兩棵二項樹的合并。 每棵樹的階數(shù)不超過 logn，因此 運行時間是 O（ log n）的。 function merge(p, q) while not( () and () ) tree = mergeTree((), ()) if not ().empty() tree = mergeTree(tree, ()) (tree) else (tree) () () () 上圖表明合并兩個二項堆的過程 。這是 連續(xù)的合并階數(shù)相同的二叉樹來實現(xiàn)的。如果合并后的二叉 樹 又和兩個二項堆中某棵二叉樹階數(shù)相同 ， 那么這兩棵二叉樹再次被合并 。 插入 可以通過簡單地創(chuàng)建一個只包含此元素 的新堆 ， 然后將它與原來的堆合并 。由于合并，插入需要 O（ log n）的時間，但它有一個攤銷時間為 O（ 1）。 查找最小節(jié)點 查找堆的最小節(jié)點可以通過查找最小二項 樹的根部。這可以再次輕松完成在 O（ log n）的時間，因為有 只有 O（ log n）的二叉樹 ， 因此要檢查的根節(jié)點不超過 O(log n)。 通過使用 指向最小節(jié) 點的指針 ，此操作的時間可以降低到 O（ 1）。 在執(zhí)行 Find操作以外的任何操作必須更新指針的值。這些操作的時間復雜度依然是 O(log n)。 刪除 最小節(jié)點 要刪除堆的最小元素，首先找到這個元素然后 從二叉樹中刪除它，獲得它的子樹的列表。 通過將子樹按照階數(shù)從小到大重新排列形成一個新堆 。然后合并這堆 與原來的堆。由于每棵樹至多有 log n 個孩子，創(chuàng)建這個新 堆 的時間復雜度 是 O（ log n） 。合并堆 的時間復雜度 是 O(log n)，所以整個刪除最小節(jié)點 操作 的時間復雜度 是 O(log n)。 function deleteMin(heap) min = ().first() for each current in () if min then min = current for each tree in () (tree) (min) merge(heap, tmp) 減小節(jié)點值 減小某個節(jié)點關鍵字之后 ，它可 能 會比其父節(jié)點的關鍵字來的小，從而違背了最小堆的性質。如果這種情況發(fā)生 ，交換 其與父節(jié)點的關鍵字，也可能交互其與祖父節(jié)點的關鍵字，重復這個操作直到最小堆的性質不再被違背。每棵 二叉樹高度至多為 log n，所以這需要 O(log n)的時間。 刪除 要從堆中刪除一個元素，減少其值至 負無窮大（即低于 堆中任意節(jié)點的關鍵字 ），然后 刪除堆中的最小節(jié)點。 性能 對于有 n 個節(jié)點的二項堆，以下操作的時間復雜度為 O(log n)： (1)插入一個新的節(jié)點 (2)查找最小節(jié)點 (3)刪除最小節(jié)點 (4)減小給定節(jié)點的關鍵字 (5)刪除指定節(jié)點 (6)合并兩個二項堆 尋找最小節(jié)點也可以 通過使用一個額外的指針在 O(1)時間內完成 。
畢業(yè)設計相關推薦
鄂ICP備17016276號-1