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