电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 斐波那契堆(一)之图文解析和C语言的实现 [打印本页]

作者: yuyang911220 时间: 2016-8-20 20:20 标题: 斐波那契堆(一)之图文解析和C语言的实现

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

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

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 source print ?

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 source print ?

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 时间: 2016-8-21 12:12

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

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)