乙文减肥左偏树的特点及其应用

2021年1月28日发(作者：弓形虫检查)
IOI2005
国家集训队论文


黄源河

左< br>偏
树
的
特
点
及
其
应
用

广东省中山市第一中学

黄源河


【摘要】

本文较详细地介绍了左偏树的特点以及它的各种操作。

第一部分提出可并堆的概念，
指出二叉堆的不足，
并引出左偏树。
第二部分
主要介绍了左偏树的定义和性质 。
第三部分详细地介绍了左偏树的各种操作，
并
给出时间复杂度分析。
第四部 分通过一道例题，
说明左偏树在当今信息学竞赛中
的应用。
第五部分对各种可并堆作了 一番比较。
最后总结出左偏树的特点以及应
用前景。


【关键字】

左偏树

可并堆

优先队列


【目录】

一、引言

.
.......... .................................................. .................................................. ....................
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
小结

.
............ .................................................. .................................................. .........
1
2
四、左偏树的应用

.
... .................................................. .................................................. .........
1
3
4.1
例
——
数字序列（
Baltic 2004
）
..... .................................................. ....................
1
3
五、左偏树与各种可并堆的比较

.
.................. .................................................. ....................
1
5
5.1
左偏树的变种——斜堆

.
...................... .................................................. .................
1
5
5.2
左偏树与二叉堆的比较

.
...................... .................................................. .................
1
6
5.3
左偏树与其他可并堆的比较

.
.................... .................................................. ...........
1
6
六、总结

.
..... .................................................. .................................................. .......................
1
8
第

1
页


共

21
页

IOI2005
国家集训队论文


黄源河

【正文】

一、引言

优先队列在信息学竞赛中十分常见，
在统计问题、
最值问题、
模拟问题和贪
心问题等等类型的题目中，
优先队列都 有着广泛的应用。
二叉堆是一种常用的优
先队列，它编程简单，效率高，但如果问题需要对两个 优先队列进行合并，二叉
堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。< br>

二、左偏树的定义和性质

在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。


2.1

优先队列，可并堆

2.1.1

优先队列的定义

优先队列
(Priority
Queue)是一种抽象数据类型
(ADT)
，它是一种容器，里面
有一些元素，这些元素也称 为队列中的节点
(node)
。优先队列的节点至少要包含
一种性质：
有序性 ，
也就是说任意两个节点可以比较大小。
为了具体起见我们假
设这些节点中都包含一个 键值
(key)
，节点的大小通过比较它们的键值而定。优
先队列有三个基本的操作： 插入节点
(Insert)
，取得最小节点
(Minimum)
和删除
最小节点
(Delete-Min)
。


2.1.2

可并堆的定义

可并堆
(Mergeable
Heap)
也是一种抽象数据类型，它除了支持优先队列的三
个基本操作
(I nsert, Minimum, Delete- Min)
，
还支持一个额外的操作——合并操作：

H
←
Merge(H
1
,H
2
)
Merge( )
构造并返 回一个包含
H
1
和
H
2
所有元素的新堆
H
。


前面已经说过，
如果我们不需要合并操作，
则二叉堆是理想的 选择。
可惜合
并二叉堆的时间复杂度为
O(n)
，用它来实现可并堆，则合并 操作必然成为算法
的瓶颈。左偏树
(Leftist
Tree)
、二项堆
(Binomial
Heap)
和
Fibonacci
堆
(Fibonacci
Heap) 都是十分优秀的可并堆。
本文讨论的是左偏树，
在后面我们将看到各种可
并堆的比 较。

第

2
页


共

21
页

IOI2005
国家集训队论文


黄源河

2.2

左偏树的定义

左偏树
(Leftist
Tree)
是一种可并堆的实现。左偏树是一棵二 叉树，它的节点
除了和二叉树的节点一样具有左右子树指针
( left, right )< br>外，
还有两个属性：
键值
和距离
(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
是为了使我们< br>可以以更小的代价在优先队列的其它两个基本操作（插入节点、删除最小节点）
进行后维持堆性质 。在后面我们就会看到它的作用。


这两条性质是对每一个节点而言的，
因 此可以简单地从中得出，
左偏树的左
右子树都是左偏树。

由这两条性质，< br>我们可以得出左偏树的定义：
左偏树是具有左偏性质的堆有
序二叉树
。


下图是一棵左偏树：

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
的缘故，
它的结构偏向左侧，
不过距离的概念和树的< br>深度并不同，左偏树并不意味着左子树的节点数或是深度一定大于右子树。


下面我们来讨论左偏树的距离和节点数的关系。


[
引理
1]
若左偏树的距离为一定值，
则节点数最少的左偏树是完全二叉树。

证明：< br>由性质
2
可知，当且仅当对于一棵左偏树中的每个节点
i
，都有

dist(left(i)) = dist(right(i))
时，
该左偏 树的节点数最少。
显然具有这样性质的二叉
树是完全二叉树。


[
定理
1]
若一棵左偏树的距离为
k
，则这棵左偏树至少 有
2
k+1
-1
个节点。

证明：
由引理
1
可知，
当这样的左偏树节点数最少的时候，
是一棵完全二叉
树。距离为k
的完全二叉树高度也为
k
，节点数为
2
k+1
-1< br>，所以距离为
k
的左偏
树至少有
2
k
＋
1< br>-1
个节点。


作为定理
1
的推论，我们有：


[
性质
4]
一棵
N
个节点的左偏树距离最多为
?
log(N+1)
?
-1
。

证明：
设一棵N
个节点的左偏树距离为
k
，由定理
1
可知，
N
≥

2
k+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
页

IOI2005
国家集训队论文


黄源河

最后，由于
right(A)
的距离可能发生改变，我们必须更新
A
的距离：

dist(A)
←
dist(right(A)) + 1

不难验证，经这样合并后的树
C
符合性质
1
和性质
2
，因此是一棵左偏树。
至此 左偏树的合并就完成了。


下图是一个合并过程的示例：


合并流程

第

6
页


共

21
页

IOI2005
国家集训队论文


黄源河

我们可以用下面的代码描述左偏树的合并过程：

Function

Merge(A, B)

If

A = NULL

Then

return
B

If

B = NULL

Then

return
A

If

key(B) < key(A)

Then

swap(A, B)

right(A)
←
Merge(right(A), B)

If

dist(right(A)) > dist(left(A))

Then



swap(left(A), right(A))

If

right(A) = NULL

Then

dist(A)
←
0

Else

dist(A)
←
dist(right(A)) + 1

return
A
End

Function


下面我们来分析合并操作的时间复杂度。
从上 面的过程可以看出，
每一次递
归合并的开始，
都需要分解其中一棵树，
总是把 分解出的右子树参加下一步的合
并。根据性质
3
，一棵树的距离决定于其右子树的距离 ，而右子树的距离在每次
分解中递减，因此每棵树
A
或
B
被分解的次 数分别不会超过它们各自的距离。
根据性质
4
，分解的次数不会超过
?
log(N
1
+1)
?
+
?
log(N
2
+1)
?
-2
，其中
N
1
和
N
2
分
别为左偏树
A
和
B< br>的节点个数。因此合并操作最坏情况下的时间复杂度为
O(
?
log(N
1
+1)
?
+
?
log(N
2
+1)
?
-2) = O(log N
1
+ log N
2
)
。


3.2

插入新节点



单节点的树一定是左偏 树，
因此向左偏树插入一个节点可以看作是对两棵左
偏树的合并。下面是插入新节点的代码：< br>
Procedure

Insert(x, A)

B ← MakeIntoTree(x)


A ← Merge(A, B)

End

Procedure




由于合并的其中一棵树只有一个节点，
因此插入新节点操作的时间复杂度是
O(logn)。

第

7
页


共

21
页

IOI2005
国家集训队论文


黄源河

3.3

删除最小节点

由性质
1
，我们知道，左偏树的根节点是最小节点。在删除根节点后，剩下
的两棵子树都是左偏树，< br>需要把他们合并。
删除最小节点操作的代码也非常简单：

Function

DeleteMin(A)

t
←
key(root(A))

A
←
Merge(left(A), right(A))

return
t
End

Function

由于删除最小节点后只需进行一次合 并，
因此删除最小节点的时间复杂度也
为
O(log
n)
。


3.4

左偏树的构建

将
n
个节点构建成一棵左偏树，这也是一个常用的操作。


算法一


暴力算法——逐个节点插入，时间复杂度为
O(n
log
n)
。


算法二


仿照二叉堆的构建算法，我们可以得到下面这种算法：

?

将
n
个节点（每个节点作为一棵左偏树）放入先进先出队列。

?

不断地从队首取出两棵左偏树，将它们合并之后加入队尾。

?

当队列中只剩下一棵左偏树时，算法结束。



1

2
3
4


5
6




3
4


5
6
1
第

8
页


共

21
页

2

IOI2005
国家集训队论文


黄源河

5
6
1
2
3
4











1
2
3
4


5
6
6

6
5
3
4
2
1
3
4


2
1
5
























构建流程



下面分析算法二的时间复杂度。假设
n=2
k
，则：


n
次和并的是两棵只有
1
个节点的左偏树。

2
n
接下来的
次合并的是两棵有
2
个节点的左偏树。

4
n
接下来的
次合并的是两棵有
4
个节点的左偏树。

8
??

n
接下来的
i
次合并的是两棵有
2
i-1
个节点的左偏树。

2
前

合并两棵2
i
个节点的左偏树时间复杂度为
O(
i
)
，因此算法 二的总时间复杂
k
n
n
n
i
k
?
2
度为：
*
O
(
1
)
?
*
O
(< br>2
)
?
*
O
(
3
)
?
?< br>?
O
(
n
*
?
i
)
?
O< br>(
n
*
(
2
?
k
))
?
O
(
n
)
。

2
4
8
2
i
?
1
2

3.5

删除任意已知节点

接下来是关于删除任意已知节点的操作 。之所以强调“已知”
，是因为这里
所说的任意节点并不是根据它的键值找出来的，
左 偏树本身除了可以迅速找到最
小节点外，不能有效的搜索指定键值的节点。故此，我们不能要求：请删除 所有
键值为
100
的节点。


前面说过，
优先队 列是一种容器。
对于通常的容器来说，
一旦节点被放进去
以后，
容器就完全拥 有了这个节点，
每个容器中的节点具有唯一的对象掌握它的
第

9
页


共

21
页

IOI2005
国家集训队论文


黄源河

拥有 权（
ownership
）
。对于这种容器的应用，优先队列只能删除最小节点，因为
你根本无从知道它的其它节点是什么。


但是优先队列除了作为一种容器外 还有另一个作用，就是可以找到最小节
点。
很多应用是针对这个功能的，
它们并没有将 拥有权完全转移给优先队列，
而
是把优先队列作为一个最小节点的选择器，
从一堆节点 中依次将它们选出来。
这
样一来节点的拥有权就可能同时被其它对象掌握。
也就是说某 个节点虽不是最小
节点，不能从优先队列那里“已知”
，但却可以从其它的拥有者那里“已知”
。


这种优先队列的应用也是很常见的。
设想我们有一个闹钟，< br>它可以记录很多
个响铃时间，
不过由于时间是线性的，
铃只能一个个按先后次序 响，
优先队列就
很适合用来作这样的挑选。
另一方面使用者应该可以随时取消一个“已知”
的响
铃时间，这就需要进行任意已知节点的删除操作了。

< br>我们的这种删除操作需要指定被删除的节点，
这和原来的删除根节点的操作
是兼容的，因 为根节点肯定是已知的。上面已经提过，在删除一个节点以后，将
会剩下它的两棵子树，它们都是左偏树 ，我们先把它们合并成一棵新的左偏树。

p ← M
erge(left(x), right(x))
现在
p
指向了这颗新的左偏树，
如果我们删除的是根节 点，
此时任务已经完
成了。
不过，
如果被删除节点
x
不是根 节点就有点麻烦了。
这时
p
指向的新树的
距离有可能比原来
x
的距离要大或小，
这势必有可能影响原来
x
的父节点
q
的距
离，
因为
q
现在成为新树
p
的父节点了。
于是就要仿照合 并操作里面的做法，
对
q
的左右子树作出调整，并更新
q
的距离。这 一过程引起了连锁反应，我们要顺
着
q
的父节点链一直往上进行调整。

q

x

p

q



新树
p
的距离为
dist(p)
，
如果
dist(p)+1
等于
q
的原有距离
dist(q)
，
那 么不管
p
是
q
的左子树还是右子树，我们都不需要对
q
进行 任何调整，此时删除操作也
就完成了。


如果
dist(p)+1
小于
q
的原有距离
dist(q)
，
那么
q
的距离必须调整为
dist(p)+1
，
而且如果
p
是左子树的话 ，
说明
q
的左子树距离比右子树小，
必须交换子树。
由
于< br>q
的距离减少了，所以
q
的父节点也要做出同样的处理。


剩下就是另外一种情况了，那就是
p
的距离增大了，使得
dist(p)+1
大于
q
的原有距离
dist(q)
。在这种情况下，如果
p
是左子树，那么
q
的距离不会改变，
第

10
页


共

21
页