Fibonacci Heap
structure
结点的定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class node{
public:
int degree;
int mark;
int key;
int id;
node* p;
node* child;
node* left;
node* right;
node(){key = 0, id = 0, degree = 0, p = NULL, child = NULL, left = this, right = this, mark = false;}
node(int key, int id):key(key),id(id){degree = 0, p = NULL, left = this, right = this, child = NULL, mark = false;}
friend class FIBONACCI_HEAP;
};
|
由于我们我们键值可能重复，我们可以加一个 来区分不同的键值，然后用一个比较函数来判断两个节点的大小
1
2
3
| bool LEQ(node* X, node* Y){
return X->key == Y->key ? X->id < Y->id : X->key < Y->key;
}
|
是标记一个节点，自从上一次成为另一个节点的孩子之后，是否失去过孩子
这个标记的定义很重要也很抽象，我们后面证明复杂度要用
同时这里 是任意的，不一定是键值最小的节点
我们称 所在的那一层(最上层)链表是根链表
MAKE_FIB_HEAP
初始化，把 设为空指针， 设成
INSERT
直接把节点插入到根链表, 复杂度为
这里 是指将 插入到 所在那一层的链表
那么我们直接 即可
然后要换根，节点数加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void INSERT_LIST(node* x, node* y){
assert(y != NULL);
x->right = y->right;
y->right->left = x;
y->right = x;
x->left = y;
}
void INSERT(int key, int id){
node* x = new node(key, id);
if(MIN == NULL){
MIN = x;
}else{
INSERT_LIST(x, MIN);
if(LEQ(x, MIN)) MIN = x;
}
NUM++;
}
|
UNION
直接将两个堆的根链表合并即可, 复杂度为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void CONCATENATE(node* X, node* Y){
node* x = X->right;
node* y = Y->right;
Y->right = x, x->left = Y;
X->right = y, y->left = X;
}
Fib UNION(Fib X, Fib Y){
if(X.MIN == NULL) return Y;
if(Y.MIN == NULL) return X;
Fib H;
H.MAKE_FIB_HEAP();
H.MIN = X.MIN;
H.CONCATENATE(H.MIN, Y.MIN);
if(LEQ(Y.MIN, X.MIN)) H.MIN = Y.MIN;
H.NUM = X.NUM + Y.NUM;
return H;
}
|
相当于 出堆顶元素，这里是小顶堆
我们在 中将 节点的所有子节点提到根链表中，将 原有节点删除，并将 指向根链表中任意一个节点
然后，我们要调用子过程 来调整整个堆
在 中，我们先创建一个辅助数组 ， 存储根链表中度数为 的节点指针
我们遍历根链表所有节点，用 表示当前节点的度数。
如果 为空，就将当前节点存入
如果我们发现两个节点度数相同，即 不为空，就将键值大的节点插入为另一节点的儿子
这里插入儿子需要换父亲和儿子指针，将父节点度数加 , 并将儿子节点 标为 , 因为他成为了另一节点的儿子，之后没有失去节点
此时 ,然后重复这一过程至 为空
的大小为 , 表示 个节点的FIBHEAP的最大度数
我们后面会证明：
最后将根链表遍历一遍换
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
| void REMOVE_LIST(node* x){
x->right->left = x->left;
x->left->right = x->right;
}
int GET_CHILD_NUMBER(node* x){
node* w = x;
int count = 0;
do{
++count;
w = w->right;
}while(w != x);
return count;
}
void LINK(node* y, node* x){
REMOVE_LIST(y);
if(x->child == NULL){
x->child = y;
y->left = y->right = y;
}else INSERT_LIST(y, x->child);
y->p = x;
++x->degree;
y->mark = false;
}
void CONSOLIDATE(){
for(int i = 0; i < LOGN; ++i) A[i] = NULL;
node* w = MIN;
int count = GET_CHILD_NUMBER(MIN);
while(count--){
node* x = w;
node* right = w->right;
int d = x->degree;
while(A[d] != NULL){
node* y = A[d];
if(LEQ(y, x)) swap(x, y);
LINK(y, x);
A[d] = NULL;
++d;
}
A[d] = x;
w = right;
}
MIN = NULL;
for(int i = 0; i < LOGN; ++i){
if(A[i] != NULL){
if(MIN == NULL) MIN = A[i];
else{
if(LEQ(A[i], MIN)) MIN = A[i];
}
}
}
}
node* EXTRACT_MIN(){
node* z = MIN;
if(z != NULL){
node* x = z->child;
if(x != NULL){
int count = GET_CHILD_NUMBER(x);
while(count--){
x->p = NULL;
node* right = x->right;
REMOVE_LIST(x);
INSERT_LIST(x, MIN);
x = right;
}
}
REMOVE_LIST(z);
if(z == z->right){
MIN = NULL;
}else{
MIN = z->right;
CONSOLIDATE();
}
NUM--;
}
return z;
}
|
DECREASE-KEY
这里我们传参会直接传一个节点指针，因为键值可能重复，而且堆本身很难查找元素
那么我们将节点 键值改为 , 然后判断是否小于父亲节点 ，如果是，就把 插入到根链表中，然后递归判断
如果 没有失去过儿子，就打上标记
如果已经失去儿子， 为 , 那么当前失去的是第 个儿子，那么我们仍然要把 插入到根链表中，然后递归判断父亲
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
| void CUT(node* x, node* y){
if(y->child == x){
node* right = (x == x->right) ? NULL : x->right;
y->child = right;
}
REMOVE_LIST(x);
y->degree--;
INSERT_LIST(x, MIN);
x->p = NULL;
x->mark = false;
}
void CASCADING_CUT(node* y){
node* z = y->p;
if(z != NULL){
if(y->mark == false) y->mark = true;
else{
CUT(y, z);
CASCADING_CUT(z);
}
}
}
void DECREASE_KEY(node* x, int k){
assert(k <= x->key);
x->key = k;
node* y = x->p;
if(y != NULL && LEQ(x, y)){
CUT(x, y);
CASCADING_CUT(y);
}
if(LEQ(x, MIN)) MIN = x;
}
|
为什么第二个儿子就要递归判断呢？
从后面复杂度证明里看，是为了保证复杂度正确
但是改成第 个儿子再递归判断，会影响复杂度吗？
理论分析不做，我们来看看实际表现：
把递归的代码改成这样：
1
2
3
4
5
6
7
8
9
10
| void CASCADING_CUT(node* y){
node* z = y->p;
if(z != NULL){
if(y->mark < MARK_TIME) y->mark++;
else{
CUT(y, z);
CASCADING_CUT(z);
}
}
}
|
一般地 MARK_TIME = 1
我们改成MARK_TIME = 2, 4, 10, 观察在 P3378 上的表现：
| MARK_TIME |
TOTAL TIME/ms |
|
777 |
|
781 |
|
777 |
|
783 |
可以看出，没啥区别
但这只是在这一题上表现没区别，不代表没有影响
我们姑且认为，MARK_TIME = 1 是为了证明复杂度而构造出来的一个比较优美的常数
看过后面复杂度证明，你应该会觉得这个设定确实挺妙的
DELETE
直接将待删除节点 为 , 再 即可
1
2
3
4
| void DELETE(node* x){
DECREASE_KEY(x, -INFTY);
EXTRACT_MIN();
}
|
复杂度
定义势能函数为, 这里 表示根链表中树的数目， 表示已标记的节点数目.
我们下面来证明 操作的摊还复杂度为 .
由于在 过程中我们要遍历整个根链表，并且要将最小节点的所有儿子提到跟链表上合并，儿子个数最大为 , 根链表中根的个数为 , 所以实际代价最大与 成正比.
抽取最小节点之前的势能为 , 抽取之后，由于 根链表最大节点数为 ，且没有其他节点被标记，所以势能函数最大为
所以摊还代价为
DECREASE-KEY
我们下面来证明 操作的摊还复杂度为 .
假定我们递归调用 的次数为 , 则实际代价为 .
在每次 过程中，我们都会切除一个节点，把他连接到根链表上，并去除他的标记
所以，最后的根链表中最多有 个根，同时最多有 个标记
所以，我们有
D(n)
我们上面说了这么多操作，其中最大的上界均为, 下面我们来证明
实际上我们是要证明：, 这里
Lemma 1: 设 是一个度数为 的节点，其儿子按插入先后顺序为 , 且 , 则有
证明： 成立。对于 , 我们插入第 个孩子，这之前 已被插入，则 , 并且插入孩子当且仅当 时，所以有 .
这之后， 最多失去一个儿子，如果失去两个儿子，它就会被从 中剪掉，所以有
这一步看出了 设定的作用，是为了构造出 这样一个不等式
Lemma 2: 斐波那契数可以被写为
证明：归纳。对 成立。
现假设, 则
Lemma 3:
证明：归纳。
对于 成立。
先假设 和
则
Lemma 4: 设任意节点 , 则
证明：设 表示度数为 的节点的最小可能
平凡地，
表示 的孩子，把 自身和第一个孩子 () 提出来，有
其中最后一步由 及 的单调性保证
这一步就用到了 的设定，构造出来了 这样一个式子，便于后面复杂度证明时用到引理中有关斐波那契数的式子
现在我们要证明
对于 成立
假设 对 成立
则我们有
最后一步由 得到
则我们有
最后一步由 得到
所以
这对于任意节点成立
所以
其实这是个常数很大的数据结构，虽然P3378比二叉堆快，但P3377比左偏堆、斜堆慢
其实这个堆挺优美的，从他这个名称来看
实现
code:
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
| class node{
public:
int degree;
int mark;
int key;
int id;
node* p;
node* child;
node* left;
node* right;
node(){key = 0, id = 0, degree = 0, p = NULL, child = NULL, left = this, right = this, mark = false;}
node(int key, int id):key(key),id(id){degree = 0, p = NULL, left = this, right = this, child = NULL, mark = false;}
friend class FIBONACCI_HEAP;
};
bool LEQ(node* X, node* Y){
return X->key == Y->key ? X->id < Y->id : X->key < Y->key;
}
class FIBONACCI_HEAP{
private:
static const int LOGN = 30;
static const int INFTY = 1e9+10;
public:
int NUM;
node* A[LOGN];
node* MIN;
void MAKE_FIB_HEAP(){
MIN = NULL;
NUM = 0;
}
void CHKDFS(node* x){
if(x == NULL) return;
node* z = x;
do{
if(x->child) assert(x->child->p == x);
assert(x->left->right==x);
assert(x->right->left==x);
CHKDFS(x->child);
x = x->right;
}while(x != z);
}
void CHECK(){
node* x = MIN;
CHKDFS(x);
}
void OUTDFS(node* x, int dep){
if(x == NULL) return;
node* z = x;
do{
cerr << x->key << " " << x->id << " " << dep << endl;
OUTDFS(x->child, dep + 1);
x = x->right;
}while(x != z);
}
void TRAVERSE(){
node* x = MIN;
OUTDFS(x, 0);
}
node* DFS(node* x, int key){
if(x == NULL) return NULL;
node* z = x;
do{
if(x->key == key){
cout<<"FOUND:"<<x->key<<" "<<key<<endl;
return x;
}
node* res = DFS(x->child, key);
if(res != NULL) return res;
x = x->right;
}while(x != z);
return NULL;
}
node* FIND(int key){
node* x = MIN;
return DFS(x, key);
}
void INSERT_LIST(node* x, node* y){
assert(y != NULL);
x->right = y->right;
y->right->left = x;
y->right = x;
x->left = y;
}
void REMOVE_LIST(node* x){
x->right->left = x->left;
x->left->right = x->right;
}
int GET_CHILD_NUMBER(node* x){
node* w = x;
int count = 0;
do{
++count;
w = w->right;
}while(w != x);
return count;
}
void INSERT(int key, int id){
node* x = new node(key, id);
if(MIN == NULL){
MIN = x;
}else{
INSERT_LIST(x, MIN);
if(LEQ(x, MIN)) MIN = x;
}
NUM++;
}
void LINK(node* y, node* x){
REMOVE_LIST(y);
if(x->child == NULL){
x->child = y;
y->left = y->right = y;
}else INSERT_LIST(y, x->child);
y->p = x;
++x->degree;
y->mark = false;
}
void CONSOLIDATE(){
for(int i = 0; i < LOGN; ++i) A[i] = NULL;
node* w = MIN;
int count = GET_CHILD_NUMBER(MIN);
while(count--){
node* x = w;
node* right = w->right;
int d = x->degree;
while(A[d] != NULL){
node* y = A[d];
if(LEQ(y, x)) swap(x, y);
LINK(y, x);
A[d] = NULL;
++d;
}
A[d] = x;
w = right;
}
MIN = NULL;
for(int i = 0; i < LOGN; ++i){
if(A[i] != NULL){
if(MIN == NULL) MIN = A[i];
else{
if(LEQ(A[i], MIN)) MIN = A[i];
}
}
}
}
node* EXTRACT_MIN(){
node* z = MIN;
if(z != NULL){
node* x = z->child;
if(x != NULL){
int count = GET_CHILD_NUMBER(x);
while(count--){
x->p = NULL;
node* right = x->right;
REMOVE_LIST(x);
INSERT_LIST(x, MIN);
x = right;
}
}
REMOVE_LIST(z);
if(z == z->right){
MIN = NULL;
}else{
MIN = z->right;
CONSOLIDATE();
}
NUM--;
}
return z;
}
void CUT(node* x, node* y){
if(y->child == x){
node* right = (x == x->right) ? NULL : x->right;
y->child = right;
}
REMOVE_LIST(x);
y->degree--;
INSERT_LIST(x, MIN);
x->p = NULL;
x->mark = false;
}
void CASCADING_CUT(node* y){
node* z = y->p;
if(z != NULL){
if(y->mark == false) y->mark = true;
else{
CUT(y, z);
CASCADING_CUT(z);
}
}
}
void DECREASE_KEY(node* x, int k){
assert(k <= x->key);
x->key = k;
node* y = x->p;
if(y != NULL && LEQ(x, y)){
CUT(x, y);
CASCADING_CUT(y);
}
if(LEQ(x, MIN)) MIN = x;
}
void DELETE(node* x){
DECREASE_KEY(x, -INFTY);
EXTRACT_MIN();
}
int GET_KEY(node* x){
return x->key;
}
int MINIMUM(){
if(MIN == NULL) return 0;
return GET_KEY(MIN);
}
int DELETE_MIN(){
node* res = EXTRACT_MIN();
if(res == NULL) return 0;
else return res->key;
}
void CONCATENATE(node* X, node* Y){
node* x = X->right;
node* y = Y->right;
Y->right = x, x->left = Y;
X->right = y, y->left = X;
}
};
typedef FIBONACCI_HEAP Fib;
Fib UNION(Fib X, Fib Y){
if(X.MIN == NULL) return Y;
if(Y.MIN == NULL) return X;
Fib H;
H.MAKE_FIB_HEAP();
H.MIN = X.MIN;
H.CONCATENATE(H.MIN, Y.MIN);
if(LEQ(Y.MIN, X.MIN)) H.MIN = Y.MIN;
H.NUM = X.NUM + Y.NUM;
return H;
}
|