肛裂便血-深圳人工流产
本资料由
-
大学生创业
|
创业
|
创业网
/
提供资料
左
偏
树
的
特
点
及其
应
用
广东省中山市第一中学
黄源河
【摘要】
本文较详细地介绍了左偏树的特点以及它的各种操作。
第一部分提出可并堆的概念，
指出二叉堆的不足，
并引出左偏树。
第二部分< br>主要介绍了左偏树的定义和性质。
第三部分详细地介绍了左偏树的各种操作，
并
给出时间复杂度分析。
第四部分通过一道例题，
说明左偏树在当今信息学竞赛中
的应用 。
第五部分对各种可并堆作了一番比较。
最后总结出左偏树的特点以及应
用前景。
【关键字】
左偏树
可并堆
优先队列
【目录】
一、引言
.< br>............................................... .................................................. .................................
2
二、左偏树的定义和性质
.
..................... .................................................. ...............................
2
2.1
优先队列，可并堆
.
........................ .................................................. .........................
2
2.1.1
优先队列的定义
.
......................... .................................................. .................
2
2.1.2
可并堆的定义
.
.......................... .................................................. ....................
2
2.2
左偏树的定义
.
.......................... .................................................. ...............................
3
2.3
左偏树的性质
.
.......................... .................................................. ...............................
4
三、左偏树的操作
.
........................ .................................................. ........................................
6
3.1
左偏树的合并
.
.................. .................................................. .......................................
6
3.2
插入新节点
.
................... .................................................. ..........................................
8
3.3
删除最小节点
.
........ .................................................. .................................................
9
3.4
左偏树的构建
.
........ .................................................. .................................................
9
3.5
删除任意已知节点
.
...... .................................................. .........................................
1
0
3.6
小结
.
........... .................................................. .................................................. ..........
1
3
四、左偏树的应用
.
.. .................................................. .................................................. ..........
1
5
4.1
例
——
数字序列（
Baltic 2004
）
..... .................................................. ....................
1
5
五、左偏树与各种可并堆的比较
.
.................. .................................................. ....................
1
8
5.1
左偏树的变种——斜堆
.
...................... .................................................. .................
1
8
5.2
左偏树与二叉堆的比较
.
...................... .................................................. .................
1
9
5.3
左偏树与其他可并堆的比较
.
.................... .................................................. ...........
1
9
六、总结
.
..... .................................................. .................................................. .......................
2
2
在线代理
|
网页代理
|
代理网页
|
减 肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减 肥瘦身药
|
本资料由
-
大学生创业
|
创业
|创业网
/
提供资料
【正文】
一、引言
< 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.2
左偏树的定义
左偏树
(Leftist
Tree)
是一 种可并堆的实现。左偏树是一棵二叉树，它的节点
除了和二叉树的节点一样具有左右子树指针
( left, right )
外，
还有两个属性：
键值
和距离
(di st)
。键值上面已经说过，是用于比较节点的大小。距离则是如下定义
的：
节点
i
称为
外节点
(external
node)
，当且仅当节点
i
的左子树或右子树为空
( left(i) = NULL
或
right(i) = NULL )
；节点
i
的
距离
(
dist(
i
)
)
是节点< br>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
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
-1
个节点。
作为定理
1
的推论，我们有：
[
性质
4]
一棵
N
个节点的左偏树距离最多为
?
log(N+1)
?
-1
。
证明：
设一棵N
个节点的左偏树距离为
k
，由定理
1
可知，
N
≥
2
k+1
-1
，因
此
k
≤
?
log(N+1)
?
-1
。
有了上面的
4
个性质，我们可以开始讨论左偏树的操作了。
在线代理
|
网页代理
|
代理网页
|
减 肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减 肥瘦身药
|
本资料由
-
大学生创业
|
创业
|创业网
/
提供资料
三、左偏树的操作
本章将讨论左 偏树的各种操作，
包括插入新节点、
删除最小节点、
合并左偏
树、
构 建左偏树和删除任意节点。
由于各种操作都离不开合并操作，
因此我们先
讨论合并操作 。
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)
在线代理
|
网页代理
|
代理网页
|
减肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减肥瘦身药
|
本资料由
-
大学生创业
|
创业|
创业网
/
提供资料
最后，由于
right(A)
的距离可能发生改变，我们必须更新
A
的距离：
dist(A)
←
dist(right(A)) + 1
不难验证，经这样合并后的树
C
符合性质
1
和性质
2
，因此是一棵左偏树。
至此左偏树的 合并就完成了。
下图是一个合并过程的示例：
合并流程
在线代理
|
网页代理
|
代理网页
|
减 肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减 肥瘦身药
|
本资料由
-
大学生创业
|
创业
|创业网
/
提供资料
我们可以用下面的代码描述左偏树的合并过程：
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)。
在线代理
|
网页代理
|
代理网页
|
减肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减肥瘦身药
|
本资料由
-
大学生创业
|
创业
|
创业网
/
提供资料
3.3
删除最小节点
由性质
1
，我们知道，左偏树的根节点是最小节点。 在删除根节点后，剩下
的两棵子树都是左偏树，
需要把他们合并。
删除最小节点操作的 代码也非常简单：
Function
DeleteMin(A)
t
←
key(root(A))
A
←
Merge(left(A), right(A))
return
t
End
Function
由于删除最小节点后只需进行一次合并，
因此删除最小节点的时间复杂度也
为
O(l og
n)
。
3.4
左偏树的构建
将
n
个节点构建成一棵左偏树，这也是一个常用的操作。
算法一
暴力算法——逐个节点插入，时间复杂度为
O(n
log
n)
。
算法二
仿照二叉堆的构建算法，我们可以得到下面这种算法：
?
将
n
个节点（每个节点作为一棵左偏树）放入先进先出队列。
?
不断地从队首取出两棵左偏树，将它们合并之后加入队尾。
?
当队列中只剩下一棵左偏树时，算法结束。
1
2
3
4
5
6
在线代理
|
网页代理
|
代理网页
|
减 肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减 肥瘦身药
|
本资料由
-
大学生创业
|
创业
|创业网
/
提供资料
3
4
5
6
1
2
2
4
3
6
5
6
5
6
1
2
3
4
1
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
的节点。
前面说过，
优先队列是一种容器。
对于通常的容器来说，
一旦 节点被放进去
以后，
容器就完全拥有了这个节点，
每个容器中的节点具有唯一的对象掌 握它的
拥有权（
ownership
）
。对于这种容器的应用，优先队列只能 删除最小节点，因为
你根本无从知道它的其它节点是什么。
但是优先队列 除了作为一种容器外还有另一个作用，就是可以找到最小节
点。
很多应用是针对这个功能的，< br>它们并没有将拥有权完全转移给优先队列，
而
是把优先队列作为一个最小节点的选择器，
从一堆节点中依次将它们选出来。
这
样一来节点的拥有权就可能同时被其它对象掌握。
也就是说某个节点虽不是最小
节点，不能从优先队列那里“已知”
，但却可以从其它的 拥有者那里“已知”
。
这种优先队列的应用也是很常见的。
设想 我们有一个闹钟，
它可以记录很多
个响铃时间，
不过由于时间是线性的，
铃只 能一个个按先后次序响，
优先队列就
很适合用来作这样的挑选。
另一方面使用者应该可 以随时取消一个
“已知”
的响
铃时间，这就需要进行任意已知节点的删除操作了。
我们的这种删除操作需要指定被删除的节点，
这和原来的删除根节点的操作< br>是兼容的，因为根节点肯定是已知的。上面已经提过，在删除一个节点以后，将
会剩下它的两棵子 树，它们都是左偏树，我们先把它们合并成一棵新的左偏树。
p ←
Merge(left(x), right(x))
现在
p
指向了这颗新 的左偏树，
如果我们删除的是根节点，
此时任务已经完
成了。
不过，
如果被删除节点
x
不是根节点就有点麻烦了。
这时
p
指向的新树的< br>距离有可能比原来
x
的距离要大或小，
这势必有可能影响原来
x
的父节点
q
的距
离，
因为
q
现在成为新树
p的父节点了。
于是就要仿照合并操作里面的做法，
对
q
的左右子树作出调 整，并更新
q
的距离。这一过程引起了连锁反应，我们要顺
着
q
的父 节点链一直往上进行调整。
q
x
p
q
新树
p
的距离为
dist(p )
，
如果
dist(p)+1
等于
q
的原有距离
d ist(q)
，
那么不管
p
是
q
的左子树还是右子树，我们 都不需要对
q
进行任何调整，此时删除操作也
就完成了。
在线代理
|
网页代理
|
代理网页
|
减 肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减 肥瘦身药
|
本资料由
-
大学生创业
|
创业
|创业网
/
提供资料
如果
dist(p)+1
小于
q
的原有距离
dist(q)
，
那么
q
的距 离必须调整为
dist(p)+1
，
而且如果
p
是左子树的话，说明
q
的左子树距离比右子树小，
必须交换子树。
由
于
q
的距离减少了，所以
q
的父节点也要做出同样的处理。
剩下就是另外一种情况了，那就是
p
的距离增大了，使得
dist(p)+1
大于
q
的原有距离
dist(q)
。在这种情况下，如果
p
是左子树，那么
q
的距离不会改变，
此时删除操作也可以结束了。
如果p
是右子树，
这时有两种可能：
一种是
p
的距
离仍小于 等于
q
的左子树距离，这时我们直接调整
q
的距离就行了；另一种是
p
的距离大于
q
的左子树距离，这时我们需要交换
q
的左右子树并调 整
q
的距离，
交换完了以后
q
的右子树是原来的左子树，
它 的距离加
1
只能等于或大于
q
的原
有距离，如果等于成立，删除操作 可以结束了，否则
q
的距离将增大，我们还要
对
q
的父节点做出相同 的处理。
删除任意已知节点操作的代码如下：
Procedure
Delete(x)
q
←
parent(x)
p
←
Merge(left(x), right(x))
parent(p)
←
q
If
q
≠
NULL
and
left(q) = x
Then
left(q)
←
p
If
q
≠
NULL
and
right(q) = x
Then
right(q)
←
p
While
q
≠
NULL
Do
If
dist(left(q)) < dist(right(q))
Then
swap(left(q), right(q))
If
dist(right(q))+1 = dist(q)
Then
Exit
Procedure
dist(q)
←
dist(right(q))+1
p
←
q
q
←
parent(q)
End
While
End
Procedure
下面分两种情况讨论删除操作的时间复杂度。
情况
1
：
p
的距离减小了。在这种情况下，由于
q
的距离只能缩小，当循环
结束时，
要么根节点处理完了，
q
为空；
要么
p
是
q
的右子树并且
dist(p)+1=dist( q)
；
如果
dist(p)+1>dist(q)
，
那么
p
一定是
q
的左子树，
否则会出现
q
的右子树距离缩
小了，但是加
1
以后却大于
q
的距离的情况，不符合左偏树的性质
3
。不论哪种
情况，删除操作都可以结束了。注意到，每一次循环，
p
的距离都 会加
1
，而在
循环体内，
dist(p)+1
最终将成为某个节点的 距离。根据性质
4
，任何的距离都不
在线代理
|
网页代理
|
代理网页
|
减肥药排行榜
|
淘宝最好的减肥药
|
什么减肥药效果最好
|
减肥瘦身药
|
肛裂便血-深圳人工流产
肛裂便血-深圳人工流产
肛裂便血-深圳人工流产
肛裂便血-深圳人工流产
肛裂便血-深圳人工流产
肛裂便血-深圳人工流产
肛裂便血-深圳人工流产
肛裂便血-深圳人工流产
本文更新与2021-01-28 04:08，由作者提供，不代表本网站立场，转载请注明出处：http://www.xapfxb.com/yuer/432133.html
-
上一篇：左偏树的特点及其应用
下一篇：东北话顺口溜