左偏堆的特点及其应用.ppt

左偏树的特点及其应用
广东省中山市第一中学黄源河
2
左偏树的定义
左偏树(Leftist Tree)是一种可并堆(Mergeable Heap) ,它除了支持优先队列的三个基本操作(插入,删除,取最小节点),还支持一个很特殊的操作——合并操作。
左偏树是一棵堆有序(Heap Ordered)二叉树。
左偏树满足左偏性质(Leftist Property)。
3
左偏树的定义——左偏性质
定义一棵左偏树中的外节点(External Node) 为左子树或右子树为空的节点。
定义节点 i 的距离(dist(i)) 为节点 i 到它的后代中,最近的外节点所经过的边数。
任意节点的左子节点的距离不小于右子节点的距离(左偏性质)。
由左偏性质可知,一个节点的距离等于以该节点为根的子树最右路径的长度。
4
左偏树的性质
定理:若一棵左偏树有N个节点,则该左偏树的距离不超过log(N+1)-1。
最右路径: A-C-G
最右路径节点数= 3
距离= 2
8个节点的左偏树的最大距离:log(8+1)-1 = 2
A
B
D
0
0
0
1
2
E
H
F
0
G
0
1
C
最右路径长度即为左偏树的距离
5
左偏树的操作
左偏树支持下面这些操作:
MakeNull ——初始化一棵空的左偏树
Merge ——合并两棵左偏树
Insert ——插入一个新节点
Min ——取得最小节点
DeleteMin ——删除最小节点
Delete ——删除任意已知节点
Decrease ——减小一个节点的键值
6
左偏树的操作——合并
合并操作是递归进行的
a < b
a
L1
R1
b
L2
R2
T1
T2
merge
合并T1和T2两棵左偏树
a
L1
merge
b
L2
R2
R1
先将T1的右子树与T2合并
7
左偏树的操作——合并
合并操作是递归进行的
a
L1
merge
b
L2
R2
R1
R’
先将T1的右子树与T2合并
a
L1
R’
8
左偏树的操作——合并
合并操作是递归进行的
a
L1
R’
dist(R’) > dist(L1)
a
L1
R’
交换左右子树并更新根节点距离
合并后的右子树距离可能大于左子树距离
9
左偏树的操作——合并
合并操作的代码如下:
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
10
左偏树的操作——合并
下面是一个合并的例子:
6
12
18
24
37
18
7
0
0
1
2
0
0
1
3
10
8
26
17
1
1
0
0
0
Merge (3, 6)