可合併優先佇列操作

隨機可合併堆（也稱為可合併優先佇列）支援許多常見操作。這些操作包括插入、刪除和搜尋操作 findMin。插入和刪除操作是根據可合併堆特有的附加操作 Meld(A1, A2) 實現的。

合併 (Meld)

合併（也稱為合併）操作的基本目標是獲取兩個堆（透過獲取每個堆的根節點），A1 和 A2，並將它們合併，返回單個堆節點作為結果。此堆節點是包含來自以 A1 和 A2 為根的兩個子樹的所有元素的堆的根節點。

此合併操作的一個優秀特性是可以遞迴定義。如果任一堆與空值相關聯，則合併透過空集完成，並且方法返回非空堆的根節點。如果 A1 和 A2 均不為空，則檢查 A1 > A2。如果是，則交換兩者。因此，可以確保 A1 < A2，並且合併堆的根節點將包含 A1。然後，我們將 A2 與 A1.left 或 A1.right 遞迴合併。此步驟是隨機化的地方，因為此合併哪一側的決定是由拋硬幣決定的。

function Meld(Node A1, Node A2)
if A1 is nil => return A2
if A2 is nil => return A1
if A1 > A2 => swap A1 and A2
if coin_toss is 0 => A1.left = Meld(A1.left, A2)
else A1.right = Meld(A1.right, A2)
return A1

插入

完成合並操作後，插入可合併堆非常簡單。首先，建立一個包含值 p 的新節點 a。然後，此新節點只需與堆的根節點合併。

function Insert(p)
Node a = new Node
a.p = p
root = Meld(a, root)
root.parent = nil
increment node count

刪除

與插入操作一樣簡單，Remove() 使用 Meld 操作將根節點從堆中刪除。這是透過簡單地合併根節點的兩個子節點並將返回的節點作為新的根節點來實現的。

function Remove()
rootNode = Meld(rootNode.left, rootNode.right)
if rootNode is not nil => rootNode.parent = nil
decrement node count

查詢最小值 (FindMin)

對於隨機可合併堆來說，FindMin() 可能是最簡單的操作，它只需返回儲存在堆根節點中的當前元素。

附加操作

可以對可合併堆應用一些額外的操作，這些操作也具有 O(logn) 最壞情況效率：

  • Remove(a) - 從堆中刪除節點 a 及其鍵。
  • Absorb(P) - 將可合併堆 P 的所有元素加到此堆中，在此過程中清空 P。
  • DecreaseKey(a, q) - 將節點 a 中的鍵減小到 q（前提條件：q <= a.p）。

更新於：2020年1月2日

490 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告