IOI2005国家集训队论文 黄源河
左偏树的特点及其应用
广东省中山市第一中学 黄源河
【摘要】
本文较详细地介绍了左偏树的特点以及它的各种操作。
第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。
【关键字】 左偏树 可并堆 优先队列
【目录】
一、引言 ................................................................................................................................... 2 二、左偏树的定义和性质 ....................................................................................................... 2
2.1 优先队列，可并堆 .................................................................................................... 2
2.1.1 优先队列的定义 ............................................................................................. 2 2.1.2 可并堆的定义 ................................................................................................. 2 2.2 左偏树的定义 ............................................................................................................ 3 2.3 左偏树的性质 ............................................................................................................ 4 三、左偏树的操作 ................................................................................................................... 5
3.1 左偏树的合并 ............................................................................................................ 5 3.2 插入新节点 ................................................................................................................ 7 3.3 删除最小节点 ............................................................................................................ 8 3.4 左偏树的构建 ............................................................................................................ 8 3.5 删除任意已知节点 .................................................................................................... 9 3.6 小结 .......................................................................................................................... 12 四、左偏树的应用 ................................................................................................................. 13
4.1 例——数字序列（Baltic 2004） ........................................................................... 13 五、左偏树与各种可并堆的比较 ......................................................................................... 15
5.1 左偏树的变种——斜堆 .......................................................................................... 15 5.2 左偏树与二叉堆的比较 .......................................................................................... 16 5.3 左偏树与其他可并堆的比较 .................................................................................. 16 六、总结 ................................................................................................................................. 18
第 1 页 共 21 页
IOI2005国家集训队论文 黄源河
【正文】
一、引言
优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。
二、左偏树的定义和性质
在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。
2.1 优先队列，可并堆 2.1.1 优先队列的定义
优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。
2.1.2 可并堆的定义
可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作：
H ← Merge(H1,H2)
Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。
前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。
第 2 页 共 21 页
IOI2005国家集训队论文 黄源河
2.2 左偏树的定义
左偏树(Leftist Tree)是一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针( left, right )外，还有两个属性：键值和距离(dist)。键值上面已经说过，是用于比较节点的大小。距离则是如下定义的：
节点i称为外节点(external node)，当且仅当节点i的左子树或右子树为空 ( left(i) = NULL或right(i) = NULL )；节点i的距离(dist(i))是节点i到它的后代中，最近的外节点所经过的边数。特别的，如果节点i本身是外节点，则它的距离为0；而空节点的距离规定为-1 (dist(NULL) = -1)。在本文中，有时也提到一棵左偏树的距离，这指的是该树根节点的距离。
左偏树满足下面两条基本性质：
[性质1] 节点的键值小于或等于它的左右子节点的键值。
即key(i)≤key(parent(i)) 这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1，我们可以知道左偏树的根节点是整棵树的最小节点，于是我们可以在O(1) 的时间内完成取最小节点操作。
[性质2] 节点的左子节点的距离不小于右子节点的距离。 即dist(left(i))≥dist(right(i)) 这条性质称为左偏性质。性质2是为了使我们可以以更小的代价在优先队列的其它两个基本操作（插入节点、删除最小节点）进行后维持堆性质。在后面我们就会看到它的作用。
这两条性质是对每一个节点而言的，因此可以简单地从中得出，左偏树的左右子树都是左偏树。
由这两条性质，我们可以得出左偏树的定义：左偏树是具有左偏性质的堆有序二叉树。
下图是一棵左偏树：
dist key 2 6 2 1 1 6 1 10 1 3 0 18
Node: key dist L R 1 12 0 0 0 0 0 0 0 18 24 37 18 21 14 17 0 33 0 0 23 26
第 3 页 共 21 页
IOI2005国家集训队论文 黄源河
2.3 左偏树的性质
在前面一节中，本文已经介绍了左偏树的两个基本性质，下面本文将介绍左偏树的另外两个性质。
我们知道，一个节点必须经由它的子节点才能到达外节点。由于性质2，一个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数，也就是说，我们有
[性质3] 节点的距离等于它的右子节点的距离加1。
即 dist( i ) = dist( right( i ) ) + 1 外节点的距离为0，由于性质2，它的右子节点必为空节点。为了满足性质3，故前面规定空节点的距离为-1。
我们的印象中，平衡树是具有非常小的深度的，这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有的节点而设计的，它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。从图中我们可以看到它并不平衡，由于性质2的缘故，它的结构偏向左侧，不过距离的概念和树的深度并不同，左偏树并不意味着左子树的节点数或是深度一定大于右子树。
下面我们来讨论左偏树的距离和节点数的关系。
[引理1] 若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。 证明：由性质2可知，当且仅当对于一棵左偏树中的每个节点i，都有 dist(left(i)) = dist(right(i)) 时，该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。
[定理1] 若一棵左偏树的距离为k，则这棵左偏树至少有2k+1-1个节点。 证明：由引理1可知，当这样的左偏树节点数最少的时候，是一棵完全二叉树。距离为k的完全二叉树高度也为k，节点数为2k+1-1，所以距离为k的左偏树至少有2k＋1-1个节点。
作为定理1的推论，我们有：
[性质4] 一棵N个节点的左偏树距离最多为?log(N+1)? -1。
证明：设一棵N个节点的左偏树距离为k，由定理1可知，N ≥ 2k+1-1，因此k ≤ ?log(N+1)? -1。
有了上面的4个性质，我们可以开始讨论左偏树的操作了。
第 4 页 共 21 页
IOI2005国家集训队论文 黄源河
三、左偏树的操作
本章将讨论左偏树的各种操作，包括插入新节点、删除最小节点、合并左偏树、构建左偏树和删除任意节点。由于各种操作都离不开合并操作，因此我们先讨论合并操作。 3.1 左偏树的合并
C ← Merge(A,B)
Merge( ) 把A,B两棵左偏树合并，返回一棵新的左偏树C，包含A和B中的所有元素。在本文中，一棵左偏树用它的根节点的指针表示。
在合并操作中，最简单的情况是其中一棵树为空（也就是，该树根节点指针为NULL）。这时我们只须要返回另一棵树。
若A和B都非空，我们假设A的根节点小于等于B的根节点（否则交换A,B），把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树right(A) 和B了。
right(A) ← Merge(right(A), B)
合并了right(A) 和B之后，right(A) 的距离可能会变大，当right(A) 的距离大于left(A) 的距离时，左偏树的性质2会被破坏。在这种情况下，我们只须要交换left(A) 和right(A)。
若dist(left(A)) > dist(right(A))，交换left(A) 和right(A)
第 5 页 共 21 页