斜堆

维基百科,自由的百科全书
跳转至: 导航搜索

斜堆左偏树的一个变种。斜堆是一棵保持堆有序的二叉树,但是它不满足左偏性质,或者说斜堆根本就没有“距离”这个概念——它不需要记录任何一个节点的距离。从结构上来说,所有的左偏树都是斜堆,但反之不然。

定义[编辑]

  • 仅有一个节点的树为斜堆;
  • 两个斜堆合并的结果仍为斜堆。

合并操作[编辑]

斜堆合并操作的递归合并过程和左偏树完全一样。假设我们要合并 A 和 B两个斜堆,且 A 的根节点比 B 的根节点小,我们只需要把 A 的根节点作为合并后新斜堆的根节点,并将 A 的右子树与 B 合并。由于合并都是沿着最右路径进行的,经过合并之后,新斜堆的最右路径长度必然增加,这会影响下一次合并的效率。所以合并后,通过交换左右子树,使整棵树的最右路径长度非常小(这是启发规则)。然而斜堆不记录节点的距离,在操作时,从下往上,沿着合并的路径,在每个节点处都交换左右子树。通过不断交换左右子树,斜堆把最右路径甩向左边了。

递归实现合并[编辑]

  • 比较两个堆; 设p是具有更小的root的键值的堆,q是另一个堆,r是合并后的结果堆。
  • 令r的root是p(具有最小root键值),r的右子树为p的左子树。
  • 令r的左子树为p的右子树与q合并的结果。

举例。合并前: SkewHeapMerge1.svg


合并后 SkewHeapMerge7.svg

非递归合并实现[编辑]

  • 把每个堆的每棵(递归意义下)最右子树切下来。这使得得到的每棵树的右子树均为空。
  • 按root的键值的升序排列这些树。
  • 迭代合并具有最大root键值的两棵树:
    • 具有次大root键值的树的右子树必定为空。把其左子树与右子树交换。现在该树的左子树为空。
    • 具有最大root键值的树作为具有次大root键值树的左子树。

举例: SkewHeapMerge1.svg

SkewHeapMerge2.svg

SkewHeapMerge3.svg

SkewHeapMerge4.svg

SkewHeapMerge5.svg

SkewHeapMerge6.svg

SkewHeapMerge7.svg

外部链接[编辑]