斐波那契堆是一种高级的堆结构,建议与二项堆一起食用效果更佳。
斐波那契堆是一个摊还性质的数据结构,很多堆操作在斐波那契堆上的摊还时间都很低,达到了θ(1)的程度,取最小值和删除操作的时间复杂度是O(lgn)。
斐波那契堆的关键操作我觉得是合并树和级联剪切。下面我简要地说一些关于这两个方法的体会。
斐波那契堆深度的增加应该就是通过合并树(consolidate)这个操作,如果没有剪切的影响,那么consolidate后的堆非常类似与二项堆。
级联剪切操作则是减小堆深度的操作,我在学习的时候一直有个问题,就是为什么级联剪切一定要失去第二个子结点时才开始剪切?为什么恰恰是二,而不是第三个或其他数?后来我看到一个大佬的博客写的是,这样可以尽量保证斐波那契堆可以类似于二项堆,防止“越剪越乱”。这个解释也是目前我最接受的。
所以可以看到的是斐波那契堆其实可以看做一个宽松的二项堆。
代码如下:(仅供参考)
1 class FibHeap {
2 private :
3 struct Node {
4 Node * parent;
5 Node * child;
6 Node * left;
7 Node * right;
8 int key;
9 int degree; //degree of children
10 bool mark; //whether lose any child
11 Node() : parent(nullptr), child(nullptr), left(this), right(this),
12 key(0), degree(0), mark(false) {}
13 };
14 private :
15 Node * min; //pointer to the minimum node of heap
16 int n;
17 private :
18 void listAdd(Node * &r, Node * p);//add p to r
19 void listdelete(Node * p);
20 void listUnion(Node * x, Node * y);//add x and y
21 int Dn() {return (log2(n) + 1);} //当所有根都合并到一棵树上时,dn最大,为log2(n), 参考二项树
22 void consolidate();
23 void heapLink(Node * y, Node * x);
24 void cut(Node * x, Node * y);
25 void cascadingCut(Node * y);
26 Node * search(Node * r, int k);//search is not good in heap
27 public :
28 FibHeap() : min(nullptr), n(0) {}
29 void insert(int k);
30 int extractMin(); //get minimum node and delete it
31 int minimum() {return min->key;}
32 void decreaseKey(Node * x, int k);
33 void remove(int k);
34 void heapUnion(FibHeap &b);
35 bool search(int k) {return (search(min, k) == nullptr ? false : true);}
36 bool empty() {return n == 0;}
37 };
38
39 void FibHeap::listAdd(Node * &r, Node * p) {
40 if (r == nullptr) {
41 r = p;
42 r->left = r;
43 r->right = r;
44 }
45 else {
46 Node * x = r; //去引用
47 p->right = x->right;
48 p->left = x;
49 x->right->left = p;
50 x->right = p;
51 }
52 }
53
54 void FibHeap::listdelete(Node * p) {
55 p->left->right = p->right;
56 p->right->left = p->left;
57 }
58
59 void FibHeap::listUnion(Node * x, Node * y) {
60 if (x == nullptr)
61 x = y;
62 else {
63 Node * tail = x->left;
64 x->left->right = y;
65 y->left->right = x;
66 x->left = y->left;
67 y->left = tail;
68 }
69 }
70
71 void FibHeap::insert(int k) {
72 Node * p = new Node;
73 p->key = k;
74 listAdd(min, p);
75 if (min->key > k) {
76 min = p;
77 }
78 ++n;
79 }
80
81 void FibHeap::heapLink(Node * y, Node * x) {
82 listdelete(y);
83 listAdd(x->child, y);
84 ++x->degree;
85 y->mark = false;
86 }
87
88 void FibHeap::consolidate() {
89 vector<Node*> a(Dn(), nullptr);
90 Node *x, *y, *z;
91 int d;
92 Node * sentry = new Node;
93 listAdd(min->left, sentry); //add a sentry
94 for (x = min; x != sentry; x = z) {
95 z = x->right; //防止x被link到y上,导致x-right无法指向正确的位置,所以先保存
96 d = x->degree;
97 while (a[d] != nullptr) {
98 y = a[d];
99 if (x->key > y->key)
100 swap(x, y);
101 heapLink(y, x);
102 a[d] = nullptr;
103 ++d;
104 }
105 a[d] = x;
106 }
107 min = nullptr;
108 for (int i = 0; i < a.size(); ++i) {
109 if (a[i] != nullptr) {
110 listAdd(min, a[i]);
111 if (a[i]->key < min->key)
112 min = a[i];
113 }
114 }
115 delete sentry;
116 }
117
118 int FibHeap::extractMin() {
119 int ret = 0;
120 Node * p = min;
121 if (p) {
122 ret = p->key;
123 if (p->child) {
124 Node * x = p->child;
125 Node * y = x->right;
126 for (int i = 0; i < p->degree; ++i) {
127 listAdd(min, x);
128 x->parent = nullptr;
129 x = y;
130 y = y->right;
131 }
132 }
133 if (p->right == p) //the child of p is empty, and p is the only one in root list
134 min = nullptr;
135 else {
136 min = p->right;
137 listdelete(p);
138 consolidate();
139 }
140 delete p;
141 --n;
142 }
143 return ret;
144 }
145
146 void FibHeap::cut(Node * x, Node * y) {
147 listdelete(x);
148 --y->degree;
149 listAdd(min, x);
150 x->parent = nullptr;
151 x->mark = false;
152 }
153
154 void FibHeap::cascadingCut(Node * y) {
155 Node * z = y->parent;
156 if (z) {
157 if (y->mark == false)
158 y->mark = true;
159 else {
160 cut(y, z);
161 cascadingCut(z);
162 }
163 }
164 }
165
166 void FibHeap::decreaseKey(Node * x, int k) {
167 if (k >= x->key)
168 return ;
169 x->key = k;
170 Node * y = x->parent;
171 if (y && y->key > x->key) {
172 cut(x, y);
173 cascadingCut(y);
174 }
175 if (x->key < min->key)
176 min = x;
177 }
178
179 void FibHeap::remove(int k) {
180 Node * p = search(min, k);
181 if (p == nullptr)
182 return ;
183 decreaseKey(p, INT_MIN);
184 extractMin();
185 }
186
187 void FibHeap::heapUnion(FibHeap &b) { //can't use b any more
188 if (b.min == nullptr)
189 return ;
190 listUnion(min, b.min);
191 if (min->key > b.min->key)
192 min = b.min;
193 n += b.n;
194 }
195
196 FibHeap::Node * FibHeap::search(Node * r, int k) {
197 if (r == nullptr)
198 return r;
199 Node * x = r, *y;
200 do {
201 if (x->key == k)
202 return x;
203 else if (x->key < k) {
204 y = search(x->child, k);
205 if (y)
206 return y;
207 }
208 x = x->right;
209 } while (x != r);
210
211 return nullptr;
212 }
原文链接: https://www.cnblogs.com/yxsrt/p/12249679.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/192602
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!