|
斐波那契堆
斐波那契堆（英語：Fibonacci heap）是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能，可用于实现合并优先队列。不涉及删除元素的操作有 的平摊时间。 Extract-Min和Delete的数目和其它相比，较小时效率更佳。稠密图每次decrease key只要 的平摊时间，和二项堆的 相比是巨大的改进。 斐波纳契堆于1984年由邁克爾·弗雷德曼与罗伯特·塔扬提出，1987年公开发表。[1]名字来源于运行时分析使用的斐波那契数。 结构斐波那契堆是由一组最小堆有序树构成的。每个節點的度数为其子節點的数目。树的度数为其根節點的度数。 斐波那契堆中的树都是有根的但是无序。每个節點x包含指向父節點的指针p[x]和指向任意一个子節點的child[x]。x的所有子節點都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个節點y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果節點y是x仅有的子節點，则left[y]=right[y]=y。 斐波那契堆中所有树的根節點也用一个双向循环链表链接起来。 使用一个指针指向斐波那契堆中最小元素。 操作建立一个新的費波那契堆此處範例中使用的程式語言為C 每个節點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;
}
插入一个節點创建一个仅包含一个節點的新的斐波纳契堆，然后执行堆合并。 查找最小的節點由于用一个指针指向了具有最小值的根節點，因此查找最小的節點是簡單的操作。 合并两个斐波纳契堆简单合并两个斐波纳契堆的根表。即把两个斐波纳契堆的所有树的根首尾衔接并置。 释放（删除）最小的節點分为三步：
降低一个節點的键值对一个節點的键值降低后，自键值降低的節點开始自下而上的迭代执行下述操作，直至到根節點或一个未被标记（marked）節點为止： 如果当前節點键值小于其父節點的键值，则把该節點及其子树摘下来作为堆的新树的根節點；其原父節點如果是被标记（marked）節點，则也被摘下来作为堆的新树的根節點；如果其原父節點不是被标记（marked）節點且不是根節點，则其原父節點被加标记。 如果堆的新树的根節點被标记（marked），则去除该标记。 删除節點把被删除節點的键值调整为负无穷小，然后执行“降低一个節點的键值”算法，然后再执行“删除最小節點”算法。 参考文献
|
||||||||||||||||||||||||||||||||||||
Portal di Ensiklopedia Dunia
