左倾堆
一、什么是左倾堆？
左倾堆（Leftist Heap），也称为左偏树（Leftist Tree）、左偏堆，最左堆等。
和二叉堆（即常见的堆，基于数组实现的完全堆）一样，左倾堆也是优先队列的一种实现方式。
只不过左倾堆具有一些特殊的性质：
- 左倾性：左倾堆中左子树的深度（或高度）都不小于右子树的深度
- 最小堆性：左倾堆通常用于实现最小堆，所以根节点通常都是最小值
为了实现左倾性，左倾堆的节点都有一个 NPL（Null Path Length）属性：
- NPL：节点到一个“最近的不满节点”的最短路径的长度。空节点的 NPL = -1
其中，“不满节点”是指左右子节点中至少有一个为 null 的节点。
而左倾堆的结构中，也有几个基本性质：
- 节点的键值 <= 它的左右子节点的键值
- 节点的左孩子的 NPL >= 节点右孩子的 NPL
- 节点的 NPL = 它的右孩子的 NPL + 1
下面是左倾堆的一个例子：
1
2
3
4
5
6
7
| 2(1)
/ \
3(1) 4(0)
/ \
5(0) 7(0)
/
9(0)
|
其中，括号中的数字表示 NPL。
像 4，5，7，9 这几个节点都有 null 子节点，所以它们的 NPL 都是 0。
而 2，3 的 NPL 则等于它们右孩子的 NPL + 1。
另外，有一点需要说明的是：根节点的 NPL 不一定比子节点的大。
二、为什么用左倾堆？
左倾堆和二叉堆的作用是一样的，只是在结构上有所区别：
- 二叉堆是用数组实现，堆结构是一棵完全二叉树
- 左倾堆是用树实现，结构就是一棵普通的二叉树
二叉堆和左倾堆都能用于优先队列的实现，区别不是很大。
- 但是在涉及“合并操作”时，二叉堆的效率会比较低，而左倾堆的性能更好
- 而左倾堆也有自己的缺点，就是在删除最小元素操作上可能表现略差一些
所以，左倾堆适用于某些特殊场景下，特别是需要频繁执行合并操作的情况。
三、怎么实现左倾堆？
合并操作是左倾堆的重点，合并两个堆的步骤如下：
- 如果两个堆中有一个为空，则直接返回另一个堆
- 如果两个堆都不为空，则比较两个堆的根节点，将较小的根节点作为新堆的根节点
- 将较小根节点的右子树和较大根节点合并，然后将合并后的树作为新堆的右子树
- 如果新堆的右子树的 NPL > 左子树的 NPL，则交换左右子树
- 新堆的 NPL = 右子树的 NPL + 1
步骤看起来挺多的，但是其实逻辑很简单，伪代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| merge(h1, h2) {
if (h1 == null) {
return h2;
}
if (h2 == null) {
return h1;
}
min = h1.val < h2.val ? h1 : h2;
max = h1.val > h2.val ? h1 : h2;
min.right = merge(min.right, max);
if (npl(min.right) > npl(min.left)) {
swap(min.left, min.right);
}
min.npl = npl(min.right) + 1;
return min;
}
|
下面给出一个合并操作的例子：
1
2
3
4
5
| 堆1 堆2
2(1) 1(1)
/ \ / \
6(0) 4(0) 3(0) 5(0)
|
1）首先，取小根节点 1(1) 作为新堆的根节点，然后合并小根右孩子与大根堆
1
2
3
4
5
| 新堆1 待合并
1(1) 5(0) 2(1)
/ / \
3(0) 6(0) 4(0)
|
2）同样地，取小根节点 2(1) 作为新堆的根节点，合并小根右孩子与大根堆
1
2
3
4
5
| 新堆1 新堆2 待合并
1(1) 2(1) 5(0) 4(0)
/ /
3(0) 6(0)
|
3）同上，取小根节点 4(0) 作为新堆根节点，合并小根右孩子（null 节点）与大根堆
1
2
3
4
5
| 新堆1 新堆2 新堆3
1(1) 2(1) 4(0)
/ / \
3(0) 6(0) 5(0)
|
4）此时 4 的右孩子 5(0) 大于左孩子 NULL(-1) 的 NPL，需要交换左右孩子
1
2
3
4
5
| 新堆1 新堆2 新堆3
1(1) 2(1) 4(0)
/ / /
3(0) 6(0) 5(0)
|
同时更新 4 的 NPL = NPL(null) + 1 = -1 + 1 = 0。
5）接着，完成后开始递归往上合并，4 返回给 2 的右孩子
1
2
3
4
5
6
7
| 新堆1 新堆2
1(1) 2(1)
/ / \
3(0) 6(0) 4(0)
/
5(0)
|
由于 4(0) 并不比 6(0) 的 NPL 大，所以不需要交换左右子节点。
同时更新 2 的 NPL = NPL(4) + 1 = 0 + 1 = 1。
6）继续合并完成后开始递归往上，2 返回给 1 的右孩子
1
2
3
4
5
6
7
8
9
| 新堆
1(1)
/ \
3(0) 2(1)
/ \
6(0) 4(0)
/
5(0)
|
7）由于 2(1) 比 3(0) 的 NPL 大，所以需要交换左右子节点
1
2
3
4
5
6
7
8
9
| 新堆
1(1)
/ \
2(1) 3(0)
/ \
6(0) 4(0)
/
5(0)
|
同时更新 1 的 NPL = NPL(3) + 1 = 0 + 1 = 1。
至此，合并操作就完成了。
至于其他的操作，比如删除和插入，实际上都是通过合并操作实现的：
- 删除最小元素：相当于删除根节点，然后合并左右子树
- 插入新元素：相当于将新元素作为一个新的左倾堆，然后两个堆合并
下面是它们的伪代码：
1
2
3
4
5
6
| removeFirst() {
temp = root;
root = merge(root.left, root.right);
temp.left = temp.right = null;
return temp.val;
}
|
1
2
3
| insert(val) {
root = merge(root, new Node<>(val));
}
|
总体来说，左倾堆的实现还是比较简单的。
参考
https://www.cnblogs.com/skywang12345/p/3638384.html
附录
左倾堆接口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
public interface LeftistHeap<T> {
void merge(LeftistHeap<T> other);
void insert(T val);
T removeFirst();
T first();
int size();
boolean isEmpty();
}
|
左倾堆实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
public class LeftistHeapNode<T> {
public T val;
public int npl;
public LeftistHeapNode<T> left;
public LeftistHeapNode<T> right;
public LeftistHeapNode(T val) {
this.val = val;
}
@Override
public String toString() {
return val.toString() + "(" + npl + ")";
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
public class LeftistHeapImpl<T extends Comparable<T>> implements LeftistHeap<T> {
private LeftistHeapNode<T> root;
private int size;
@Override
public void merge(LeftistHeap<T> other) {
if (!(other instanceof LeftistHeapImpl<T>)) {
return;
}
root = merge(root, ((LeftistHeapImpl<T>) other).root);
size += other.size();
}
@Override
public void insert(T val) {
root = merge(root, new LeftistHeapNode<>(val));
size++;
}
@Override
public T removeFirst() {
if (size <= 0) {
throw new IllegalStateException("Heap is Empty!");
}
LeftistHeapNode<T> node = root;
root = merge(root.left, root.right);
node.left = node.right = null;
size--;
return node.val;
}
@Override
public T first() {
if (size <= 0) {
throw new IllegalStateException("Heap is Empty!");
}
return root.val;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size <= 0;
}
private LeftistHeapNode<T> merge(LeftistHeapNode<T> h1, LeftistHeapNode<T> h2) {
if (h1 == null) {
return h2;
}
if (h2 == null) {
return h1;
}
LeftistHeapNode<T> min, max;
if (h1.val.compareTo(h2.val) <= 0) {
min = h1;
max = h2;
} else {
min = h2;
max = h1;
}
min.right = merge(min.right, max);
if (npl(min.right) > npl(min.left)) {
LeftistHeapNode<T> tmp = min.left;
min.left = min.right;
min.right = tmp;
}
min.npl = npl(min.right) + 1;
return min;
}
private int npl(LeftistHeapNode<T> node) {
return node != null ? node.npl : -1;
}
}
|