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

yuyang911220

概要本章介绍斐波那契堆。和以往一样，本文会先对斐波那契堆的理论知识进行简单介绍，然后给出C语言的实现。后续再分别给出C++和Java版本的实现；实现的语言虽不同，但是原理如出一辙，选择其中之一进行了解即可。若文章有错误或不足的地方，请不吝指出！
出处：http://www.cnblogs.com/skywang12345/p/3659060.html
更多内容：数据结构与算法系列 目录
斐波那契堆的介绍斐波那契堆(Fibonacci heap)是堆中一种，它和二项堆一样，也是一种可合并堆；可用于实现合并优先队列。斐波那契堆比二项堆具有更好的平摊分析性能，它的合并操作的时间复杂度是O(1)。
与二项堆一样，它也是由一组堆最小有序树组成，并且是一种可合并堆。
与二项堆不同的是，斐波那契堆中的树不一定是二项树；而且二项堆中的树是有序排列的，但是斐波那契堆中的树都是有根而无序的。

斐波那契堆的基本操作1. 基本定义
view sourceprint?

01.typedef int Type;
02.

03.typedef struct _FibonacciNode
04.{
05.Type   key;                     // 关键字(键值)
06.int degree;                     // 度数
07.struct _FibonacciNode *left;    // 左兄弟
08.struct _FibonacciNode *right;   // 右兄弟
09.struct _FibonacciNode *child;   // 第一个孩子节点
10.struct _FibonacciNode *parent;  // 父节点
11.int marked;                     //是否被删除第1个孩子(1表示删除，0表示未删除)
12.}FibonacciNode, FibNode;


FibNode是斐波那契堆的节点类，它包含的信息较多。key是用于比较节点大小的，degree是记录节点的度，left和right分别是指向节点的左右兄弟，child是节点的第一个孩子，parent是节点的父节点，marked是记录该节点是否被删除第1个孩子(marked在删除节点时有用)。
view sourceprint?

1.typedef struct _FibonacciHeap{
2.int   keyNum;                   // 堆中节点的总数
3.int   maxDegree;                // 最大度
4.struct _FibonacciNode *min;     // 最小节点(某个最小堆的根节点)
5.struct _FibonacciNode **cons;   // 最大度的内存区域
6.}FibonacciHeap, FibHeap;


FibHeap是斐波那契堆对应的类。min是保存当前堆的最小节点，keyNum用于记录堆中节点的总数，maxDegree用于记录堆中最大度，而cons在删除节点时来暂时保存堆数据的临时空间。
下面看看斐波那契堆的内存结构图。

从图中可以看出，斐波那契堆是由一组最小堆组成，这些最小堆的根节点组成了双向链表(后文称为'根链表')；斐波那契堆中的最小节点就是'根链表中的最小节点'！
PS. 上面这幅图的结构和测试代码中的'基本信息'测试函数的结果是一致的；你可以通过测试程序来亲自验证！
2. 插入操作
插入操作非常简单：插入一个节点到堆中，直接将该节点插入到'根链表的min节点'之前即可；若被插入节点比'min节点'小，则更新'min节点'为被插入节点。

上面是插入操作的示意图。
斐波那契堆的根链表是'双向链表'，这里将min节点看作双向联表的表头(后文也是如此)。在插入节点时，每次都是'将节点插入到min节点之前(即插入到双链表末尾)'。此外，对于根链表中最小堆都只有一个节点的情况，插入操作就很演化成双向链表的插入操作。
此外，插入操作示意图与测试程序中的'插入操作'相对应，感兴趣的可以亲自验证。
插入操作代码
view sourceprint?

01./*
02.* 将'单个节点node'加入'链表root'之前
03.*   a …… root
04.*   a …… node …… root
05.*
06.* 注意： 此处node是单个节点，而root是双向链表
07.*/
08.static void fib_node_add(FibNode *node, FibNode *root)
09.{
10.node->left        = root->left;
11.root->left->right = node;
12.node->right       = root;
13.root->left        = node;
14.}
15.

16./*
17.* 将节点node插入到斐波那契堆heap中
18.*/
19.static void fib_heap_insert_node(FibHeap *heap, FibNode *node)
20.{
21.if (heap->keyNum == 0)
22.heap->min = node;
23.else
24.{
25.fib_node_add(node, heap->min);
26.if (node->key < heap->min->key)
27.heap->min = node;
28.}
29.heap->keyNum++;
30.}

yuchengze

很好 的算法介绍，路过帮顶，感谢分享