斐波那契堆

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

斐波那契堆

斐波那契堆斐波那契堆（）是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能，可用于实现合并优先队列。不涉及删除元素的操作有 formula_1 的平摊时间。 Extract-Min和Delete的数目和其它相比，较小时效率更佳。稠密图每次decrease key只要 formula_1 的平摊时间，和二项堆的 formula_3 相比是巨大的改进。斐波纳契堆于1984年由迈克尔·弗雷德曼与罗伯特·塔扬提出，1987年公开发表。名字来源于运行时分析使用的斐波那契数。结构. 斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。斐波那契堆中的树都是有根的但是无序。每个节点"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），则去除该标记。删除节点. 把被删除节点的键值调整为负无穷小，然后执行“降低一个节点的键值”算法，然后再执行“删除最小节点”算法。

洛伦兹变换

链接器

双端队列

邻接矩阵

函式库

爱因斯坦场方程

洛伦兹力

李远哲

随机函数

万维网联盟

永济市

指南针