斐波那契堆（Fibonacci Heap）

article/2025/8/29 17:39:12

也许我们每个人都知道斐波那契数列（Fibonacci sequence）。即这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...,如果我们用伪代码比表示:

int FibonacciSequence(int n){if (n == 1 || n == 2) {return 1;}return FibonacciSequence(n - 1) + FibonacciSequence(n - 2);
}
接下来我们会知道为什么叫斐波那契堆，本文不涉及任何的分析（这里平摊分析（Amortized analysis））。

1. 概述

一个斐波那契堆是一系列具有最小堆序的有根树的集合。（也就是每棵树都遵循最小堆性质）[1]

2. 斐波那契堆的结构

[2]

从上面我们可能发现，我们堆斐波那契堆的描述，并不完全符合我们的定义（那时因为定义是针对在一次extractMin（删除最小值）操作后，使之符合我们的定义）。但从上面的结构图我们很容易看出其详细的结构，以及指针域。兄弟节点之间用双向链表进行链接，父节点指向其中一个孩子节点，而所有的子节点都会指向其父亲节点。有些节点还被标记了（后面我们会知道，只有当父节点失去孩子节点时，会被标记）。上述还有一个隐含的关键字那就是每个节点的度（即拥有孩子节点的个数）

3. 基本数据结构

typedef int ElemType;// the structure of each node of this heap
typedef struct FiboNode{// the key_valueElemType data;struct FiboNode *p;struct FiboNode *child;struct FiboNode *left;struct FiboNode *right;// the number of its childrenint degree;// indicates whether the node lost a childint marked;
} FiboNode;

// generate a node
FiboNode * generateFiboNode(ElemType data) {FiboNode * fn = NULL;fn = (FiboNode *) malloc(sizeof(FiboNode));if (fn != NULL) {fn->p = NULL;fn->child = NULL;fn->left = NULL;fn->right = NULL;fn->data = data;fn->marked = FALSE;} else {printf("memory allocation of FiboNode failed");}return fn;
}

// represent the fibonacci heap
typedef struct FibonacciHeap{// pointer pointing to min key in the heapFiboNode *min;// the number of nodes the heap containingint n;
} *FibonacciHeap;

// create Fibonacci Heap, and return it
FibonacciHeap makeFiboHeap() {FibonacciHeap h = NULL;h = (struct FibonacciHeap *) malloc(sizeof(struct FibonacciHeap));if (h == NULL) {printf("memory allocation of FibonacciHeap failed");}h->min = NULL;h->n = 0;return h;
}

4. 插入

插入其实很简单，就是把待插入的元素插入根列表(root list)中去，即上图[2]中min[H]指向的那一行。

// union two heap
FibonacciHeap heapUnion(FibonacciHeap *h1, FibonacciHeap *h2) {// using a new heapFibonacciHeap h = makeFiboHeap();if (h != NULL) {// concatenate the root list of h with h1 and h2if ((*h1)->min == NULL) {h->min = (*h2)->min;} else if ((*h2)->min == NULL) {h->min = (*h1)->min;} else {FiboNode *min_h1 = (*h1)->min;FiboNode *min_right_h1 = min_h1->right;FiboNode *min_h2 = (*h2)->min;FiboNode *min_right_h2 = min_h2->right;min_h1->right = min_right_h2;min_right_h2->left = min_h1;min_h2->right = min_right_h1;min_right_h1->left = min_h2;if ((*h1)->min->data > (*h2)->min->data) {h->min = (*h2)->min;} else {h->min = (*h1)->min;}}// release the free memoryfree(*h1);*h1 = NULL;free(*h2);*h2 = NULL;// update the nh->n = (*h1)->n + (*h2)->n;}return h;
}

5. 合并（Union）

这个操作只需要将两个斐波那契堆的根列表合并，并使得min[H]指向两者间的最小值节点。
 

// union two heap
FibonacciHeap heapUnion(FibonacciHeap *h1, FibonacciHeap *h2) {// using a new heapFibonacciHeap h = makeFiboHeap();if (h != NULL) {// concatenate the root list of h with h1 and h2if ((*h1)->min == NULL) {h->min = (*h2)->min;} else if ((*h2)->min == NULL) {h->min = (*h1)->min;} else {FiboNode *min_h1 = (*h1)->min;FiboNode *min_right_h1 = min_h1->right;FiboNode *min_h2 = (*h2)->min;FiboNode *min_right_h2 = min_h2->right;min_h1->right = min_right_h2;min_right_h2->left = min_h1;min_h2->right = min_right_h1;min_right_h1->left = min_h2;if ((*h1)->min->data > (*h2)->min->data) {h->min = (*h2)->min;} else {h->min = (*h1)->min;}}// release the free memoryfree(*h1);*h1 = NULL;free(*h2);*h2 = NULL;// update the nh->n = (*h1)->n + (*h2)->n;}return h;
}


6. 抽取最小节点


从上面我们很容易知道如何操作的。
1）具体步骤如下：
step1. 让最小节点的的所有子节点添加到根列表中去。
step2. 从根列表中删除最小节点。
step3. 创建一个log(n) + 1 的节点指针数组A。
step4. 对根列表进行合并，使得其满足我们堆斐波那契堆的定义（即根列表中的节点的度数具有唯一性）

// extract minimum node in this heap
FiboNode * extractMinimum(FibonacciHeap h) {// the minimum nodeFiboNode * z = h->min;if (z != NULL) {FiboNode * firstChid = z->child;// add the children of minimum node to the root list.if (firstChid != NULL) {FiboNode * sibling = firstChid->right;// min_right point the right node of minimum nodeFiboNode * min_right = z->right;// add the first child to the root listz->right = firstChid;firstChid->left = z;min_right->left = firstChid;firstChid->right = min_right;firstChid->p = NULL;min_right = firstChid;while (firstChid != sibling) {// record the right sibling of siblingFiboNode *sibling_right = sibling->right;z->right = sibling;sibling->left = z;sibling->right = min_right;min_right->left = sibling;min_right = sibling;sibling = sibling_right;// update the psibling->p = NULL;}}// remove z from the root listz->left->right = z->right;z->right->left = z->left;// the root list has only one nodeif (z == z->right) {h->min = NULL;// the children of z shoud be the root list of the heap// and find the minimum in this heapif (z->child != NULL) {FiboNode *child = z->child;h->min = child;FiboNode *sibling = child->right;while (child != sibling) {if (h->min->data > sibling->data) {h->min = sibling;}sibling = sibling->right;}}} else {h->min = z->right;consolidate(h);}h->n -= 1;}return z;}

2）对根列表进行合并
1. link操作
把节点y链接到x：并把y从根列表中删除，此时x会成为y的父亲，y会成为x的孩子，同时x节点的度数（degree）会增加1.

// make y a child of x
void heapLink(FibonacciHeap h, FiboNode *y, FiboNode *x) {// remove y from the root list of hy->left->right = y->right;y->right->left = y->left;// make y a child of x, incrementing x.degreeFiboNode * child = x->child;if (child == NULL) {x->child = y;y->left = y;y->right = y;} else {y->right = child->right;child->right->left = y;y->left = child;child->right = y;}y->p = x;x->degree += 1;y->marked = FALSE;
}

2. 合并
创建一个辅助数组A[0, 1..., D(H.n)]来记录根节点对应的度数的轨迹。如果A[i] = y, 则degree[y] = i.通过遍历根列表，若对应度数的数组A[i]为NILL，表示还没有记录，则使得A[i] = y, 否则存在两个度数相同的度数的根列表节点，则我们需要对其进行link操作，使之度数增加1，并设置A[i] = NILL, 然后再探查A[i + 1]是否为NIll, 为NILL则记录，否则再进行link操作，这样循环往复。

void consolidate(FibonacciHeap h) {int dn = (int)(log(h->n) / log(2)) + 1;FiboNode * A[dn];int i;for (i = 0; i < dn; ++i) {A[i] = NULL;}// the first node we will consolidateFiboNode *w  = h->min;// the final node in this heap we will consolidateFiboNode *f = w->left;FiboNode *x = NULL;FiboNode *y = NULL;int d;// tempFiboNode *t = NULL;while (w != f) {d = w->degree;x = w;w = w->right;while (A[d] != NULL) {// another node with the same degree as xy = A[d];if(x->data > y->data) {t = x;x = y;y = t;}heapLink(h, y, x);A[d] = NULL;d += 1;}A[d] = x;}// the last node to consolidate (f == w)d = w->degree;x = w;while (A[d] != NULL) {// another node with the same degree as xy = A[d];if(x->data > y->data) {t = x;x = y;y = t;}heapLink(h, y, x);A[d] = NULL;d += 1;}A[d] = x;int min_key = 100000;h->min = NULL;// to get min in this heapfor (i = 0; i < dn; ++i) {if(A[i] != NULL && A[i]->data < min_key) {h->min = A[i];min_key = A[i]->data;}}
}


7. 降低节点的值

直接上代码这样，接下来分析才比较容易。 

// decrease the data of given node to the key
void heapDecreaseKey(FibonacciHeap h, FiboNode *x, ElemType key) {if (key >= x->data) {printf("new key is's smaller than original value");return;}x->data = key;FiboNode *y = x->p;// if x->data >= y->data, do nothing// else we need cutif (y != NULL && x->data < y->data) {cut(h, x, y);cascadingCut(h, y);}// get min node of this heapif (x->data < h->min->data) {h->min = x;}
}

// if we cut node x from y, it indicates root list of
// h not null
void cut(FibonacciHeap h, FiboNode *x, FiboNode *y) {// remove x from child list of y, decrementing degree[y]if(y->degree == 1) {y->child = NULL;} else {x->left->right = x->right;x->right->left = x->left;// update child[y]y->child = x->right;}// add x to the root list of hx->left = h->min;x->right = h->min->right;h->min->right = x;x->right->left = x;// updating p[x], marked[x] and decrementing degree[y]x->p = NULL;x->marked = FALSE;y->degree -= 1;
}
void cascadingCut(FibonacciHeap h, FiboNode *y) {FiboNode *z = y->p;if (z != NULL) {if (y->marked == FALSE) {y->marked = TRUE;} else {cut(h, y, z);cascadingCut(h, z);}}
}
通过上面的发现我们知道：
1）当我们降低节点x的值时，值一定要小于当前节点x的值
2）若节点x的值比其父亲要小，则已经满足不了最小堆性质
3）当不满足最小堆性质的时候，我们要将其与其父亲y切断，并将x添加到根列表中去
4）若x的父亲在失去第一个孩子的时候则要Mark = true，当y失去第2个孩子，则y要和y的父亲z切断，接着这样不断上升操作。

8. 删除

删除的操作比较简单，就两步：
1）将节点的值降低到无穷小
2）进行extractMinimum() 操作
void heapDelete(FibonacciHeap h, FiboNode *x) {
    heapDecreaseKey(h, x, -10000);
    extractMinimum(h);
}




参考：

[1] Thomas H.Cormen、Charles E.Leiserson《算法导论》第三版 第十九章 “斐波那契对” p291
[2]  Thomas H.Cormen、Charles E.Leiserson《算法导论》第三版 第十九章 “斐波那契对” p291
[2]  Thomas H.Cormen、Charles E.Leiserson《算法导论》第三版 第十九章 “斐波那契对” p295


感谢 Thomas H.Cormen、Charles E.Leiserson等人
若有参考遗漏的请抱歉，也请您留言
若其中有误的请多多留言不甚感激


完整源码，请点击





注：转载请注明






http://chatgpt.dhexx.cn/article/RtWW1Cd1.shtml

相关文章

斐波那契堆(一)之 图文解析 和 C语言的实现

斐波那契堆(一)之 图文解析 和 C语言的实现

出自&#xff1a;http://www.cnblogs.com/skywang12345/p/3659060.html 斐波那契堆(一)之 图文解析 和 C语言的实现 概要 本章介绍斐波那契堆。和以往一样&#xff0c;本文会先对斐波那契堆的理论知识进行简单介绍&#xff0c;然后给出C语言的实现。后续再分别给出C和Java版本…
阅读更多...
斐波那契堆的C++实现

斐波那契堆的C++实现

本文改编自《算法导论》第三版第19章&#xff1a;斐波那契堆。文中代码为书中伪代码的C实现&#xff0c;如有疏漏还请指出。 1.斐波那契堆的结构 斐波那契堆是一种可并堆&#xff0c;它支持以下操作&#xff1a; ( 1 ) (1) (1)在 O ( 1 ) O(1) O(1)时间内插入元素、获取最小…
阅读更多...
常见电子元器件检测方法。——Arvin

常见电子元器件检测方法。——Arvin

电子设备中使用着大量各种类型的电子元器件&#xff0c;设备发生故障大多是由于电子元器件失效或损坏引起的。因此怎么正确检测电子元器件就显得尤其重要&#xff0c;这也是电子维修人员必须掌握的技能。我在电器维修中积累了部分常见电子元器件检测经验和技巧&#xff0c;供大…
阅读更多...
电工电子复习题

电工电子复习题

1、应用叠加定理时&#xff0c;理想电压源不作用时视为______&#xff0c; 理想电流源不作用时视为____。 2、电容元件具有“通_____隔_____”的特性&#xff0c; 电感元件具有通___阳___ ”的特性&#xff0c;。 3、已知:“u 60sin(628t -135度)(v),则其有效值为____V,角频率为…
阅读更多...
我的元器件入门

我的元器件入门

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 元器件 前言一、电阻器1、什么是电阻器2、电阻的标示方法和测量方法3、电阻的特性4、基本参数5、电阻的功能 二、电容器1、什么是电容&#xff1f;组成&#xff0c;基本参数&…
阅读更多...
2023年天津中德应用技术大学专升本机械电子工程专业考试大纲

2023年天津中德应用技术大学专升本机械电子工程专业考试大纲

天津中德应用技术大学 机械电子工程专业&#xff08;高职升本科&#xff09; 2023年专业基础考试大纲 备注&#xff1a;考试题型&#xff1a;填空题、选择题、判断题、问答题、分析题、设计与计算题 《机械设计基础》主要知识点 第一部分常用机构 一、平面机构运动分析 知…
阅读更多...
2021中级维修电工证考试题库2021职业技能鉴定

2021中级维修电工证考试题库2021职业技能鉴定

题库来源：特种作业模考题库小程序 1.三相负载作Y接时，无论负载对称与否，线电流总等于相电流。 √ 2.双向晶闸管是( )半导体结构。 B A.四层 B.五层 C.三层 D.二层 3.符合有“0”得“0”，全“1”得“1”的逻辑关系的逻辑门是( )。 B A.或门 B.与门 C.非门 D.或非门 4.示波…
阅读更多...
2018第八届至2022年第十三届蓝桥杯单片机开放与设计省赛客观题及简解整理

2018第八届至2022年第十三届蓝桥杯单片机开放与设计省赛客观题及简解整理

前言&#xff1a; 由于本人马上要参加第十四届蓝桥杯单片机设计与开发的省赛了&#xff0c;在对客观题复习两轮后&#xff0c;发现效率是比较低的&#xff0c;因此整理了2018至2022年的省赛客观题&#xff0c;将大概的考点划分三部分&#xff0c;这样可以更加系统的复习其内容。…
阅读更多...
晶体管频率特性——高频等效模型、频率特性、π模型的单向化

晶体管频率特性——高频等效模型、频率特性、π模型的单向化

晶体管高频等效模型 通过之前的定性分析得出在高频情况下晶体管结电容将对信号传输带来较大影响。之前的 h 参数等效模型没有考虑结电容的影响&#xff0c;因此不再适用&#xff0c;此时要用新的模型来反映晶体管的结电容&#xff0c;这就是高频等效模型。 此时从晶体管的实际…
阅读更多...
[渝粤教育] 郑州航空工业管理学院 电工电子技术基础 参考 资料

[渝粤教育] 郑州航空工业管理学院 电工电子技术基础 参考 资料

教育 -电工电子技术基础-章节资料考试资料-郑州航空工业管理学院【】 小节测试 1、【判断题】任何一个完整的电路都必须有电源、负载和中间环节三个基本部分组成。 A、正确 B、错误 参考资料【 】 2、【判断题】电路的作用是对电能进行传输、分配和转换&#xff1b;而对电信号进…
阅读更多...
服务于期末考试的计算机硬件基础资料

服务于期末考试的计算机硬件基础资料

电路的基本概念和基本定律 电流和电路模型 理想元件、理想电路、集总参数元件、集总参数电路 集总元件&#xff1a; 当电路器件的尺寸远小于电路最高工作频率所对应的波长时&#xff0c;可以认为元件的参数“集总”于一个点上&#xff0c;形成所谓的集总参数元件。 理想元件&am…
阅读更多...
您需要了解的跨阻放大器——第1部分

您需要了解的跨阻放大器——第1部分

跨阻放大器（TIA）是光学传感器（如光电二极管）的前端放大器，用于将传感器的输出电流转换为电压。跨阻放大器的概念很简单，即运算放大器（op amp）两端的反馈电阻（RF）使用欧姆定律VOUT= I RF 将电流（I）转换为电压（VOUT）。在这一系列博文中，我将介绍如何补偿TIA，及如…
阅读更多...
小白的模拟电路初步学习20日打卡（11）

小白的模拟电路初步学习20日打卡（11）

放大电路分析 一.基本共射放大电路的波形分析 输入电压。并且Ic等于βIb&#xff0c;所以本图可以表示Ic动态信号驮载在静态工作点上变化方向与之前的IbIc不同&#xff0c;但是是有关联的&#xff0c;即与其反向。 而这同时也是电压输出波形&#xff0c;所以可知共射放大电路…
阅读更多...
8.1 正弦波振荡电路（1）

8.1 正弦波振荡电路（1）

正弦波振荡电路是在没有外加输入信号的情况下&#xff0c;依靠电路自激振荡而产生正弦波输出电压的电路。它广泛地应用于测量、遥控、通讯、自动控制、热处理和超声波电焊等加工设备之中&#xff0c;也作为模拟电子电路的测试信号。 一、概述、 1、产生正弦波振荡的条件 在负…
阅读更多...
【长篇肝文7万字】模电/数电/单片机/计算机组成原理/电力电子常见笔试/面试题（合集）未完更新ing

【长篇肝文7万字】模电/数电/单片机/计算机组成原理/电力电子常见笔试/面试题（合集）未完更新ing

目录 一、模拟电子电路 1、基尔霍夫定理的内容 2、描述反馈电路的概念&#xff0c;列举它们的应用。 2.1 反馈的定义&#xff1a; 2.2 反馈的分类&#xff1a; 2.2.1 按反馈的效果分&#xff1a; 2.2.2 按反馈量的类型分&#xff1a; 2.3 负反馈电路 2.3.1 负反馈电路…
阅读更多...
反相、同相比例运算电路与基尔霍夫电流定律的关联分析

反相、同相比例运算电路与基尔霍夫电流定律的关联分析

基尔霍夫电流定律&#xff08;KCL&#xff09; 在任一瞬间&#xff0c;流向任一结点的电流等于流出该结点的电流。 At any given moment, the current flowing into any node is equal to the current flowing out of it. 即&#xff1a; 或&#xff1a; 反相比例运算电路…
阅读更多...
【电路与电子技术】笔记 （完结）

【电路与电子技术】笔记 （完结）

前言 是自己复习的笔记。截图是老师的课件。 大标题按章节来分。 跳过了很多东西。 2021.11.2回来补充&#xff0c;考完了&#xff0c;谢谢老师的4.0&#xff1b; 第一章 1.电路和电路模型 集总参数电路模型&#xff1a; 当实际电路的尺寸远小于其使用时最高工作频率所对应…
阅读更多...
模电笔记4 半导体三极管及放大电路基础

模电笔记4 半导体三极管及放大电路基础

4.1半导体三极管 4.1.1BJT的结构简介 结构特点&#xff1a; 、、- 表示掺杂浓度的高低 4.1.2放大状态下BJT的工作原理 发射结正偏&#xff0c;发射区向基区注入载流子&#xff0c;基区有了大量与原基区少数载流子相同极性的载流子&#xff0c;从而集电区收集到大量载流子&am…
阅读更多...
双极型晶体管及其放大电路

双极型晶体管及其放大电路

双极型晶体管及其放大电路 半导体基本特性.双极型晶体管结构与工作原理工作组态与性质 放大电路放大电路基础知识基本共射放大电路的工作原理与分析方法图解法分析:等效电路法 静态工作点稳定问题稳定原理静态工作点计算交流指标的计算 晶体单管放大电路三种组态共集放大电路共…
阅读更多...
多级放大电路超详细分析

多级放大电路超详细分析

多级放大电路多由共射、共基、共集电路组成。我们通过将电路分别分析来计算放大倍数。 并且对于三大基本电路的放大倍数计算方法需要熟练掌握 共射 共集 共基 多级放大倍数分析 多级放大电路分析 第一题 2. 若信号经电路一放大后&#xff0c;再经电路二输出 第二级电路静态工…
阅读更多...
推荐文章

Copyright @ 2022~2023