斐波那契堆 - 格物

百科正文

斐波纳契堆于1984年由迈克尔·弗雷德曼与罗伯特·塔扬提出，1987年公开发表。名字来源于运行时分析使用的斐波那契数。

结构

斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。

斐波那契堆中的树都是有根的但是无序。每个节点x包含指向父节点的指针p[x]和指向任意一个子节点的child[x]。x的所有子节点都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果节点y是x仅有的子节点，则left[y]=right[y]=y。

斐波那契堆中所有树的根节点也用一个双向循环链表链接起来。

使用一个指针指向斐波那契堆中最小元素。

操作

建立一个新的费波那契堆

此处示例中使用的编程语言为C
每个节点x的域
父节点p[x]

指向任一子女的指针child[x]——节点x的子女被链接成一个环形双链表，称为x的子女表

左兄弟left[x]

右兄弟right[x]——当left[x] = right[x] = x时，说明x是独子。

子女的个数degree[x]
布尔值域mark[x]——标记是否失去了一个孩子
//斐波那契节点ADT
typedef struct FibonacciHeapNode {
int key; //节点
int degree; //度
FibonacciHeapNode *left; //左兄弟
FibonacciHeapNode *right; //右兄弟
FibonacciHeapNode *parent; //父节点
FibonacciHeapNode *child; //第一个孩子节点
bool marked; //是否被删除第1个孩子
} FibNode;

对于一个给定的斐波那契堆H，可以通过指向包含最小关键字的树根的指针min[H]来访问，这个节点被称为斐波那契堆中的最小节点。如果一个斐波那契堆H是空的，则min[H] = NIL. 在一个斐波那契堆中，所有树的根都通过left和right指针链接成一个环形的双向链表，称为堆的根表。于是，指针min[H]就指向根表中具有最小关键字的节点。

//斐波那契堆ADT
typedef struct FibonacciHeap {
int keyNum; //堆中节点个数
FibonacciHeapNode *min;//最小堆，根节点
int maxNumOfDegree; //最大度
FibonacciHeapNode **cons;//指向最大度的内存区域
} FibHeap;

创建一个空的费波那契堆，过程MAKE-FIB-HEAP 分配并返回一个费波那契堆对象H；

//初始化一个空的Fibonacci Heap
FibHeap *FibHeapMake {
return calloc(1, sizeof(FibHeap));
//初始化节点x
FibNode * FibHeapNodeMake {

FibNode *x = (FibNode *)calloc(1, sizeof(FibNode));

x->left = x->right = x;

return x;

插入一个节点

创建一个仅包含一个节点的新的斐波纳契堆，然后执行堆合并。

查找最小的节点

由于用一个指针指向了具有最小值的根节点，因此查找最小的节点是简单的操作。

合并两个斐波纳契堆

简单合并两个斐波纳契堆的根表。即把两个斐波纳契堆的所有树的根首尾衔接并置。

释放（删除）最小的节点

分为三步：

查找最小的根节点并删除它，其所有的子节点都加入堆的根表，即它的子树都成为堆所包含的树；

需要查找并维护堆的最小根节点，但这耗时较大。为此，同时完成堆的维护：对堆当前包含的树的度数从低到高，迭代执行具有相同度数的树的合并并实现最小树化调整，使得堆包含的树具有不同的度数。这一步使用一个数组，数组下标为根节点的度数，数组的值为指向该根节点指针。如果发现具有相同度数的其他根节点则合并两棵树并维护该数组的状态。

对当前堆的所有根节点查找最小的根节点。