斐波那契堆是一种高级的堆结构，建议与二项堆一起食用效果更佳。
斐波那契堆是一个摊还性质的数据结构，很多堆操作在斐波那契堆上的摊还时间都很低，达到了θ（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】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/326368
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
