可合并优先队列操作

随机可合并堆（也称为可合并优先队列）支持许多常见操作。这些操作包括插入、删除和搜索操作 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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告