清风明月的笔记

斐波那契堆的C语言实现

斐波那契堆与二项堆的区别
名称由来及最大度数
插入操作
合并操作
删除最小元素操作
减小节点值
增加节点值
删除节点
完整源码
测试程序的运行结果

斐波那契堆同二项堆一样,也是一种可合并堆。斐波那契堆的优势是：不涉及删除元素的操作仅需要O（1）的平摊运行时间。和二项堆一样，斐波那契堆由一组树构成。这种堆松散地基于二项堆，说松散是因为：如果不对斐波那契堆做任何DECREASE-KEY 或 DELETE 操作，则堆中每棵树就和二项树一样；但是如果执行这两种操作，在一些状态下必须要破坏二项树的特征，比如DECREASE-KEY或DELETE 后，有的树高为k，但是结点个数却少于2^k，这种情况下，堆中的树不是二项树。

与二项堆相比，斐波那契堆同样是由一组最小堆有序树构成，但是斐波那契堆中的树都是有根而无序的，也就是说，单独的树满足最小堆特性，但是堆内树与树之间是无序的，如下图。

对于斐波那契堆上的各种可合并操作，关键思想是尽可能久地将工作推后。例如，当向斐波那契堆中插入新结点或合并两个斐波那契堆时，并不去合并树，而是将这个工作留给EXTRACT-MIN操作。

二项堆和斐波那契堆对于search操作的支持均比较低效；可能花费一段时间才能找到关键字。理论上来讲，对于extreact-min和delete操作相对于其他操作少的情况下，斐波那契堆确实提高了很大的效率。但是实际中，除了某些需要管理大量数据的应用外，对于大多数应用，斐波那契堆的常数因子和变程复杂性使得它比起普通二项堆并不是那么适用。

算法导论中提到，最小生成树与寻找单源最短路径的快速算法必须使用到斐波那契堆。

斐波那契堆与二项堆的区别

斐波那契堆是一种基于二项堆的松散数据结构。它与二项堆不同的地方在于：

root list和任何结点的child list使用双向循环链表，而且这些lists中的结点不再有先后次序（二项堆中root list的根结点按degree从小到大顺序，child list的结点按degree从大到小顺序）；
二项堆中任何一颗二项树中根结点的degree是最大的，而斐波那契堆中由于decrease-key操作(cut和cascading cut)的缘故，并不能保证根结点的degree最大；
二项堆中任何结点（degree等于k的）为根的子树中，结点总数为2^k；斐波那契堆中相应的结点总数下界为F{k+2}，上界为2^k（如果没有 Extract-Min和Delete两类操作的话）。其中F{k+2}表示Fibonacci数列（即0,1,1,2,3,5,8,11...）中第 k+2个Fibonacci数。注意不像二项堆由二项树组成那样，Fibonacci堆的 root list中的每棵树并不是Fibonacci树（Fibonacci树属于AVL树）。
基于上面的区别，若斐波那契堆中结点总数为n，那么其中任何结点（包括非根结点）的degree最大值不超过 D(n) = floor(lgn/lg1.618)，这里1.618表示黄金分割率(goldren ratio)，即方程x^2=x+1的一个解。所以在Extract-Min的consolidate操作之后，root list中的结点最多有D(n)+1。而二项堆中degree最大值不超过floor(lgn)，从而root list中最多有floor(lgn)+1颗二项树。
另外一个与二项堆的最大不同之处在于：Fibonacci Heap是一种具有平摊意义上的高性能数据结构。除了Extract-Min和Delete两类操作具有平摊复杂度O(lgn)，其他的操作(insert，union，find- min，decrease-key）的平摊复杂度都是常数级。因此如果有一系列的操作，其中Extract-min和delete操作个数为p，其他操作个数为q，p < q，那么总的平摊复杂度为O(p + q.lgn)。达到这个复杂度的原因有以下几点，第一，root list和任何结点的child list中使用了双向循环链表；第二，union和insert操作的延迟合并，从而在所有的可合并堆中，Fibonacci heap的合并开销O(1)最小的；第三，decrease-key中cut和cascading cut的巧妙处理（即任何非根结点最多失去一个孩子）。

名称由来及最大度数

斐波那契堆的名称来由于每棵树的最小结点数满足斐波那契数列。由于节点中marked值的限制，每个非根节点最多失去一个孩子，所以每树的最小结点数有斐波那契数列的特征，这个在算法导论中有说明，应该并不难理解。

最大度数: 斐波那契堆中的其中一棵树，如果有n个结点，则结点的最大度数D(n) = lgn(向下取整)，证明原理可以看算法导论。但在使用最大度数计算数组长度时需要加1，因为有个零度的。

数据结构

typedef struct fibonacci_node_s {  
    Item data;
    int degree;
    fibonacci_node_pt left;
    fibonacci_node_pt right;
    fibonacci_node_pt child;
    fibonacci_node_pt parent;
    int marked;
} fibonacci_node_t;

typedef struct fibonacci_heap_s *fibonacci_heap_pt;

typedef struct fibonacci_heap_s {
    /* 堆的节点总数 */
    int num;

    /* 堆的最小树根节点 */
    fibonacci_node_pt min;

    /* 堆的节点链表的最大度值，根据节点总数计算取得 */
    int   maxdegree;

    /* 
     * 节点的指针数组空间
     * 用于根链表合并调整时暂存数据，减少每次合并链表操作申请空间的消耗
     */
    fibonacci_node_pt *cons; 
} fibonacci_heap_t;

fibonacci_node_t是斐波那契堆的节点类。其中data是节点中的数据，degree是记录节点的度，left和right分别是指向节点的左右兄弟，child是节点的第一个孩子，parent是节点的父节点，marked是记录该节点是否自从上一次成为另一个结点的孩子后，是否失去过孩子。删除点后进行级联剪切时将用到这个值。

插入操作

插入新节点在斐波那契堆中非常简单，将新的节点当做一棵新的树的根插入到根表中即可。如下图所示：

以下为实现代码

static void 
fib_node_add(fibonacci_node_pt root, fibonacci_node_pt node)
{
    node->left = root->left;
    root->left->right = node;

    root->left = node;
    node->right = root;
}

void 
fib_heap_push(fibonacci_heap_pt heap, Item element)
{
    fibonacci_node_pt node;
    if (heap == NULL) {
        return;
    }

    node = fib_node_new(element);
    if (node == NULL) {
        return;
    }

    if (heap->num == 0) {
        heap->min = node;
        node->left = node;
        node->right = node;
    }
    else {
        fib_node_add(heap->min, node);
        if (item_cmp(heap->min->data, node->data)) {
            heap->min = node;
        }
    }
    heap->num++;

}

合并操作

合并两个斐波那契堆的操作也很简单，可以分为两步：

将两个根表通过指针合并为一个根表
更新min，只需要比较两个堆的min，取较小的即可

如下图所示：

以下为实现代码

/* 
 *        Name:  fib_node_cat
 * Description:  把双链表n2连接到n1上
 * 
 */
static void 
fib_node_cat(fibonacci_node_pt n1, fibonacci_node_pt n2)
{
    fibonacci_node_pt tmp;
    tmp = n1->right;
    n1->right = n2->right;
    n2->right->left = n1;

    n2->right = tmp;
    tmp->left = n2;
}

fibonacci_heap_pt 
fib_heap_union(fibonacci_heap_pt h1, fibonacci_heap_pt h2)
{
    if (h1 == NULL) {
        return h2;
    }
    if (h2 == NULL) {
        return h1;
    }

    if (h1->min == NULL) {
        free(h1);
        return h2;
    }
    else if (h2->min == NULL) {
        free(h2);
        return h1;
    }
    else {
        fib_node_cat(h1->min, h2->min);
        if (item_cmp(h1->min->data, h2->min->data)) {
            h1->min = h2->min;
        }
        h1->num += h2->num;
        free(h2);
        return h1;
    }
}

删除最小元素操作

抽取最小结点的操作是斐波那契堆中较复杂的操作。

将要抽取最小结点的子树都直接串联在根表中；
合并所有degree相等的树，直到没有相等的degree的树。

过程如下图所示(这个算法导论的示例图就解析得很清楚)：

把最小节点所在树的所有子树连接到根链表上。

移除最小节点

遍历合并所有根链表中degree相等的树。

图十一

图十二

图十三

以下为实现代码

/* 
 *        Name:  fib_heap_link
 * Description:  把两棵树合并为新树，返回合并好的树
 * 
 */
static fibonacci_node_pt 
fib_heap_link(fibonacci_node_pt n1, fibonacci_node_pt n2)
{
    fibonacci_node_pt root, child;
    if (item_cmp(n2->data, n1->data)) {
        root = n1;
        child = n2;
    }
    else {
        root = n2;
        child = n1;
    }

    if (root->child == NULL) {
        root->child = child;
        child->left = child->right = child;
    }
    else {
        //fib_node_add(root->child, child);
        child->right = root->child;
        child->left = root->child->left;
        root->child->left->right = child;
        root->child->left = child;
        root->child = child;
    }

    child->parent = root;
    root->degree++;
    child->marked = 0;
    return root;
}

/* 
 *        Name:  fib_node_remove
 * Description:  从node的双向链表中移除节点node
 * 
 */
static void 
fib_node_remove(fibonacci_node_pt node)
{
    node->right->left = node->left;
    node->left->right = node->right;
}

/* 
 *        Name:  fib_heap_cons_make
 * Description:  生成堆的双链表调节所需要的空间
 * 
 */
static void 
fib_heap_cons_make(fibonacci_heap_pt heap)
{
    int maxdegree = ceil(log((double)heap->num)/log(2.0));

    if (heap->maxdegree >= maxdegree) {
        return;
    }
    heap->maxdegree = maxdegree;

    heap->cons = (fibonacci_node_pt*)realloc(heap->cons, sizeof(fibonacci_heap_pt) * (heap->maxdegree + 1));
}

/* 
 *        Name:  fib_heap_consolidate
 * Description:  堆的链表调整合并
 * 
 */
static void 
fib_heap_consolidate(fibonacci_heap_pt heap)
{
    int d, i;
    fibonacci_node_pt pos, next;

    fib_heap_cons_make(heap);
    memset(heap->cons, 0, sizeof(fibonacci_heap_pt) * (heap->maxdegree+1));

    pos = heap->min;
    next = pos->right;
    do {
        d = pos->degree;
        while (heap->cons[d] != NULL) {
            pos = fib_heap_link(pos, heap->cons[d]);
            heap->cons[d] = NULL;
            d = pos->degree;
        }
        heap->cons[d] = pos;
        pos = next;
        next = next->right;
    } while (pos != heap->min);

    heap->min = NULL;

    for (i=0; i < heap->maxdegree + 1; i++) {
        if (heap->cons[i] != NULL) {
            if (heap->min == NULL) {
                heap->min = heap->cons[i];
                heap->min->left = heap->min->right = heap->min;
            }
            else {
                fib_node_add(heap->min, heap->cons[i]);
                if (item_cmp(heap->min->data, heap->cons[i]->data)) {
                    heap->min = heap->cons[i];
                }
            }

        }
    }

}

/* 
 *        Name:  fib_childlink_to_heaplink
 * Description:  把子树的双链表连接到堆的双链表
 * 
 */
static void 
fib_childlink_to_heaplink(fibonacci_node_pt heaplink, fibonacci_node_pt childlink)
{
    fibonacci_node_pt pos;
    if (childlink == NULL) {
        return;
    }
    //修改min指向儿子的双链表中的parent指针
    pos = childlink;
    while (pos != NULL) {
        pos->parent = NULL;
        pos = pos->right;
        if (pos == childlink) {
            break;
        }
    }
    //把child指向的双链表连接到min指向的双链表上
    fib_node_cat(heaplink, childlink);

}

void 
fib_heap_pop(fibonacci_heap_pt heap)
{
    fibonacci_node_pt min;
    if (heap == NULL || heap->min == NULL) {
        return;
    }


    min = heap->min;

    fib_childlink_to_heaplink(min, min->child);

    fib_node_remove(min);

    heap->num--;
    if (min->right == min) {
        heap->min = NULL;
    }
    else {
        heap->min = min->right;
        fib_heap_consolidate(heap);
    }
    free(min);
}

减小节点值

减少斐波那契堆中的节点的键值，这个操作的难点是：如果减少节点后破坏了"最小堆"性质，如何去维护。

首先，将以"被减小节点"为根的子树从"最小堆"中剥离出来，然后将该树关联到根链表中。
接着，对"被减少节点"的原父节点进行"级联剪切"。所谓"级联剪切"，就是在被减小节点破坏了最小堆性质，并被切下来之后；再从"它的父节点"进行递归级联剪切操作。级联操作的步骤：若父节点(被减小节点的父节点)的marked标记为false，则将其设为true，然后退出。否则，将父节点从最小堆中切下来(方式和"切被减小节点的方式"一样)；然后递归对祖父节点进行"级联剪切"。 marked标记的作用就是用来标记"该节点的子节点是否有被删除过"，它的作用是来实现级联剪切。而级联剪切的真正目的是为了防止"最小堆"由二叉树演化成链表。
最后，对根链表的最小节点进行更新。

如下图所示：

以下为实现代码

/* 
 *        Name:  fib_heap_cut
 * Description:  把堆heap中其中一个树的子节点node切下连接到堆的双链表中
 * 
 */
static void 
fib_heap_cut(fibonacci_heap_pt heap, fibonacci_node_pt node, fibonacci_node_pt parent)
{
    if (node == node->right) {
        parent->child = NULL;
    }
    else {
        fib_node_remove(node);
        parent->child = node->right;
    }
    parent->degree--;

    node->parent = NULL;
    node->marked = 0;
    fib_node_add(heap->min, node);

}

/* 
 *        Name:  fib_heap_cascading_cut
 * Description:  对堆heap的node节点进行级联剪切
 * 
 */
static void 
fib_heap_cascading_cut(fibonacci_heap_pt heap, fibonacci_node_pt node)
{
    if (node == NULL || node->parent == NULL) {
        return;
    }

    if (node->marked == 0) {
        node->marked = 1;
    }
    else {
        fib_heap_cut(heap, node, node->parent);
        fib_heap_cascading_cut(heap, node->parent);
    }

}

/* 
 *        Name:  fib_heap_decrease
 * Description:  堆heap的node节点值减少为element
 * 
 */
static void 
fib_heap_decrease(fibonacci_heap_pt heap, fibonacci_node_pt node, Item element)
{
    fibonacci_node_pt parent;

    if (heap == NULL || heap->min == NULL || node == NULL) {
        return;
    }

    node->data = element;
    parent = node->parent;

    if (parent != NULL && item_cmp(parent->data, node->data)) {
        fib_heap_cut(heap, node, parent);
        //fib_heap_export_dot(heap, "decrease2.dot", "图2");
        fib_heap_cascading_cut(heap, parent);
    }

    if (item_cmp(heap->min->data, node->data)) {
        heap->min = node;
    }

}

增加节点值

增加节点值和减少节点值类似，这个操作的难点也是如何维护"最小堆"性质。思路如下：

将"被增加节点"的"左孩子和左孩子的所有兄弟"都链接到根链表中。
接下来，把"被增加节点"添加到根链表；但是别忘了对其进行级联剪切。

如下图所示：

以下为实现代码

/* 
 *        Name:  fib_heap_increase
 * Description:  堆heap的node节点值增加为element
 * 
 */
static void
fib_heap_increase(fibonacci_heap_pt heap, fibonacci_node_pt node, Item element) 
{
    fibonacci_node_pt parent;

    fib_childlink_to_heaplink(heap->min, node->child);
    node->data = element;
    node->degree = 0;
    node->child = NULL;

    parent = node->parent;

    if (parent != NULL) {
        fib_heap_cut(heap, node, parent);
        fib_heap_cascading_cut(heap, parent);
    }
    else if (item_cmp(heap->min->data, node->data)) {
        heap->min = node;
    }
}

删除节点

先将被删除节点的键值减少。减少后的值要比"原最小节点的值"即可。
取出最小节点

以下为实现代码

void 
fib_heap_delete(fibonacci_heap_pt heap, Item element)
{
    fibonacci_node_pt node;
    Item value;
    if (heap == NULL || heap->min == NULL) {
        return;
    }
    node = fib_node_search(heap->min, element);
    if (node == NULL) {
        return;
    }

    value = heap->min->data;
    fib_heap_decrease(heap, node, value - 1);
    fib_heap_pop(heap);
}

完整源码

/* fibonacci_heap.h */
#ifndef FIBONACCI_HEAP_H
#define FIBONACCI_HEAP_H

typedef int Item;

typedef struct fibonacci_node_s *fibonacci_node_pt;

typedef struct fibonacci_node_s {  
    Item data;
    int degree;
    fibonacci_node_pt left;
    fibonacci_node_pt right;
    fibonacci_node_pt child;
    fibonacci_node_pt parent;
    int marked;
} fibonacci_node_t;

typedef struct fibonacci_heap_s *fibonacci_heap_pt;

typedef struct fibonacci_heap_s {
    /* 
     * 堆的节点总数
     */
    int num;

    /* 
     * 堆的最小树根节点
     */
    fibonacci_node_pt min;

    /* 
     * 堆的节点链表的最大度值，根据节点总数计算取得
     */
    int   maxdegree;

    /* 
     * 节点的指针数组空间
     * 用于根链表合并调整时暂存数据，减少每次合并链表操作申请空间的消耗
     * 
     */
    fibonacci_node_pt *cons; 
} fibonacci_heap_t;


fibonacci_heap_pt fib_heap_new();
fibonacci_heap_pt fib_heap_union(fibonacci_heap_pt h1, fibonacci_heap_pt h2);
void fib_heap_push(fibonacci_heap_pt heap, Item element);
int fib_heap_top(fibonacci_heap_pt heap, Item *value);
void fib_heap_pop(fibonacci_heap_pt heap);
void fib_heap_update(fibonacci_heap_pt heap, Item oldelement, Item newelement);
void fib_heap_delete(fibonacci_heap_pt heap, Item element);
void fib_heap_destroy(fibonacci_heap_pt heap);
void fib_heap_print(fibonacci_heap_pt heap);
void fib_heap_export_dot(fibonacci_heap_pt heap, char *filename, char *label);

#endif

fibonacci_heap.h

/* fibonacci_heap.c */
/*
 * =====================================================================================
 *
 *       Filename:  fibonacci_heap.c
 *
 *    Description:  斐波那契堆实现
 *
 *        Version:  1.0
 *        Created:  2016-10-02 19:58
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  simon
 *
 * =====================================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "fibonacci_heap.h"

/* 
 * 最小堆 ((a) > (b))
 * 最大堆 ({a} < (b))
 * 
 */
#define item_cmp(a, b) ((a) > (b)) /* 最小堆 */
#define item_equal(a, b) ((a) == (b)) /* 相等比较 */

static fibonacci_node_pt fib_node_new(Item element);
static void fib_node_cat(fibonacci_node_pt n1, fibonacci_node_pt n2);
static void fib_node_add(fibonacci_node_pt n1, fibonacci_node_pt n2);
static fibonacci_node_pt fib_heap_link(fibonacci_node_pt n1, fibonacci_node_pt n2);
static void fib_node_remove(fibonacci_node_pt node);
static void fib_heap_cons_make(fibonacci_heap_pt heap);
static void fib_heap_consolidate(fibonacci_heap_pt heap);
static void fib_childlink_to_heaplink(fibonacci_node_pt heaplink, fibonacci_node_pt childlink);
static fibonacci_node_pt fib_node_search(fibonacci_node_pt root, Item element);
static void fib_heap_cut(fibonacci_heap_pt heap, fibonacci_node_pt node, fibonacci_node_pt parent);
static void fib_heap_cascading_cut(fibonacci_heap_pt heap, fibonacci_node_pt node);
static void fib_heap_decrease(fibonacci_heap_pt heap, fibonacci_node_pt node, Item element);
static void fib_heap_increase(fibonacci_heap_pt heap, fibonacci_node_pt node, Item element);
static void fib_node_destroy(fibonacci_node_pt node);
static void fib_node_printnode(fibonacci_node_pt node, int h);
static void fib_node_print(fibonacci_node_pt node, int h);
static void export_dot(FILE *fp, fibonacci_node_pt node, char *last_label, char *tree_first_label);

static fibonacci_node_pt 
fib_node_new(Item element)
{
    fibonacci_node_pt node;
    if (node == NULL) {
        printf("Error: make fibonacci node failed.\n");
        return NULL;
    }
    node = (fibonacci_node_pt)malloc(sizeof(fibonacci_node_t));

    node->data   = element;
    node->degree = 0;
    node->left   = NULL;
    node->right  = NULL;
    node->child  = NULL;
    node->parent = NULL;
    node->marked = 0;
}

fibonacci_heap_pt
fib_heap_new()
{
    fibonacci_heap_pt heap;
    heap = (fibonacci_heap_pt)malloc(sizeof(fibonacci_heap_t));
    if (heap == NULL) {
        printf("Error: make fibonacci heap failed.\n");
        return NULL;
    }

    heap->num = 0;
    heap->min = NULL;
    heap->maxdegree = 0;
    heap->cons = NULL;

    return heap;
}


/* 
 *        Name:  fib_node_cat
 * Description:  把双链表n2连接到n1上
 * 
 */
static void 
fib_node_cat(fibonacci_node_pt n1, fibonacci_node_pt n2)
{
    fibonacci_node_pt tmp;
    tmp = n1->right;
    n1->right = n2->right;
    n2->right->left = n1;

    n2->right = tmp;
    tmp->left = n2;
}

fibonacci_heap_pt 
fib_heap_union(fibonacci_heap_pt h1, fibonacci_heap_pt h2)
{
    if (h1 == NULL) {
        return h2;
    }
    if (h2 == NULL) {
        return h1;
    }

    if (h1->min == NULL) {
        free(h1);
        return h2;
    }
    else if (h2->min == NULL) {
        free(h2);
        return h1;
    }
    else {
        fib_node_cat(h1->min, h2->min);
        if (item_cmp(h1->min->data, h2->min->data)) {
            h1->min = h2->min;
        }
        h1->num += h2->num;
        free(h2);
        return h1;
    }
}

static void 
fib_node_add(fibonacci_node_pt root, fibonacci_node_pt node)
{
    node->left = root->left;
    root->left->right = node;

    root->left = node;
    node->right = root;
}

void 
fib_heap_push(fibonacci_heap_pt heap, Item element)
{
    fibonacci_node_pt node;
    if (heap == NULL) {
        return;
    }

    node = fib_node_new(element);
    if (node == NULL) {
        return;
    }

    if (heap->num == 0) {
        heap->min = node;
        node->left = node;
        node->right = node;
    }
    else {
        fib_node_add(heap->min, node);
        if (item_cmp(heap->min->data, node->data)) {
            heap->min = node;
        }
    }
    heap->num++;

}

int
fib_heap_top(fibonacci_heap_pt heap, Item *value)
{
    if (heap == NULL || heap->min == NULL || value == NULL) {
        return 0;
    }

    *value = heap->min->data;
    return 1;
}

static fibonacci_node_pt 
fib_heap_link(fibonacci_node_pt n1, fibonacci_node_pt n2)
{
    fibonacci_node_pt root, child;
    if (item_cmp(n2->data, n1->data)) {
        root = n1;
        child = n2;
    }
    else {
        root = n2;
        child = n1;
    }

    if (root->child == NULL) {
        root->child = child;
        child->left = child->right = child;
    }
    else {
        //fib_node_add(root->child, child);
        child->right = root->child;
        child->left = root->child->left;
        root->child->left->right = child;
        root->child->left = child;
        root->child = child;
    }

    child->parent = root;
    root->degree++;
    child->marked = 0;
    return root;
}

/* 
 *        Name:  fib_node_remove
 * Description:  从node的双向链表中移除节点node
 * 
 */
static void 
fib_node_remove(fibonacci_node_pt node)
{
    node->right->left = node->left;
    node->left->right = node->right;
}

/* 
 *        Name:  fib_heap_cons_make
 * Description:  生成堆的双链表调节所需要的空间
 * 
 */
static void 
fib_heap_cons_make(fibonacci_heap_pt heap)
{
    int maxdegree = ceil(log((double)heap->num)/log(2.0));

    if (heap->maxdegree >= maxdegree) {
        return;
    }
    heap->maxdegree = maxdegree;

    heap->cons = (fibonacci_node_pt*)realloc(heap->cons, sizeof(fibonacci_heap_pt) * (heap->maxdegree + 1));
}

/* 
 *        Name:  fib_heap_consolidate
 * Description:  堆的链表调整合并
 * 
 */
static void 
fib_heap_consolidate(fibonacci_heap_pt heap)
{
    int d, i;
    fibonacci_node_pt pos, next;

    fib_heap_cons_make(heap);
    memset(heap->cons, 0, sizeof(fibonacci_heap_pt) * (heap->maxdegree+1));

    pos = heap->min;
    next = pos->right;
    do {
        d = pos->degree;
        while (heap->cons[d] != NULL) {
            pos = fib_heap_link(pos, heap->cons[d]);
            heap->cons[d] = NULL;
            d = pos->degree;
        }
        heap->cons[d] = pos;
        pos = next;
        next = next->right;
    } while (pos != heap->min);

    heap->min = NULL;

    for (i=0; i < heap->maxdegree + 1; i++) {
        if (heap->cons[i] != NULL) {
            if (heap->min == NULL) {
                heap->min = heap->cons[i];
                heap->min->left = heap->min->right = heap->min;
            }
            else {
                fib_node_add(heap->min, heap->cons[i]);
                if (item_cmp(heap->min->data, heap->cons[i]->data)) {
                    heap->min = heap->cons[i];
                }
            }

        }
    }

}

/* 
 *        Name:  fib_childlink_to_heaplink
 * Description:  把子树的双链表连接到堆的双链表
 * 
 */
static void 
fib_childlink_to_heaplink(fibonacci_node_pt heaplink, fibonacci_node_pt childlink)
{
    fibonacci_node_pt pos;
    if (childlink == NULL) {
        return;
    }
    //修改min指向儿子的双链表中的parent指针
    pos = childlink;
    while (pos != NULL) {
        pos->parent = NULL;
        pos = pos->right;
        if (pos == childlink) {
            break;
        }
    }
    //把child指向的双链表连接到min指向的双链表上
    fib_node_cat(heaplink, childlink);

}

void 
fib_heap_pop(fibonacci_heap_pt heap)
{
    fibonacci_node_pt min;
    if (heap == NULL || heap->min == NULL) {
        return;
    }


    min = heap->min;

    fib_childlink_to_heaplink(min, min->child);

    fib_node_remove(min);

    heap->num--;
    if (min->right == min) {
        heap->min = NULL;
    }
    else {
        heap->min = min->right;
        fib_heap_consolidate(heap);
    }
    free(min);
}


static fibonacci_node_pt 
fib_node_search(fibonacci_node_pt root, Item element)
{
    fibonacci_node_pt pos, res = NULL;

    if (root == NULL) {
        return NULL;
    }

    pos = root;
    do {
        if (item_equal(pos->data, element)) {
            res = pos;
            break;
        }
        else if (item_cmp(element, pos->data)) {
            if ((res = fib_node_search(pos->child, element)) != NULL) {
                break;
            }
        }
        pos = pos->right;
    } while (pos != root);
    return res;
}

/* 
 *        Name:  fib_heap_cut
 * Description:  把堆heap中其中一个树的子节点node切下连接到堆的双链表中
 * 
 */
static void 
fib_heap_cut(fibonacci_heap_pt heap, fibonacci_node_pt node, fibonacci_node_pt parent)
{
    if (node == node->right) {
        parent->child = NULL;
    }
    else {
        fib_node_remove(node);
        parent->child = node->right;
    }
    parent->degree--;

    node->parent = NULL;
    node->marked = 0;
    fib_node_add(heap->min, node);

}

/* 
 *        Name:  fib_heap_cascading_cut
 * Description:  对堆heap的node节点进行级联剪切
 * 
 */
static void 
fib_heap_cascading_cut(fibonacci_heap_pt heap, fibonacci_node_pt node)
{
    if (node == NULL || node->parent == NULL) {
        return;
    }

    if (node->marked == 0) {
        node->marked = 1;
    }
    else {
        fib_heap_cut(heap, node, node->parent);
        fib_heap_cascading_cut(heap, node->parent);
    }

}

/* 
 *        Name:  fib_heap_decrease
 * Description:  堆heap的node节点值减少为element
 * 
 */
static void 
fib_heap_decrease(fibonacci_heap_pt heap, fibonacci_node_pt node, Item element)
{
    fibonacci_node_pt parent;

    if (heap == NULL || heap->min == NULL || node == NULL) {
        return;
    }

    node->data = element;
    parent = node->parent;

    if (parent != NULL && item_cmp(parent->data, node->data)) {
        fib_heap_cut(heap, node, parent);
        fib_heap_cascading_cut(heap, parent);
    }

    if (item_cmp(heap->min->data, node->data)) {
        heap->min = node;
    }

}

/* 
 *        Name:  fib_heap_increase
 * Description:  堆heap的node节点值增加为element
 * 
 */
static void
fib_heap_increase(fibonacci_heap_pt heap, fibonacci_node_pt node, Item element) 
{
    fibonacci_node_pt parent;

    fib_childlink_to_heaplink(heap->min, node->child);
    node->data = element;
    node->degree = 0;
    node->child = NULL;

    parent = node->parent;

    if (parent != NULL) {
        fib_heap_cut(heap, node, parent);
        fib_heap_cascading_cut(heap, parent);
    }
    else if (item_cmp(heap->min->data, node->data)) {
        heap->min = node;
    }
}

void 
fib_heap_update(fibonacci_heap_pt heap, Item oldelement, Item newelement)
{
    fibonacci_node_pt node;

    if (heap == NULL || heap->min == NULL) {
        return;
    }
    if (item_equal(oldelement, newelement)) {
        return;
    }

    node = fib_node_search(heap->min, oldelement);

    if (node == NULL) {
        return;
    }

    if (item_cmp(oldelement, newelement)) {
        fib_heap_decrease(heap, node, newelement);
    }
    else {
        fib_heap_increase(heap, node, newelement);
    }

}

void 
fib_heap_delete(fibonacci_heap_pt heap, Item element)
{
    fibonacci_node_pt node;
    Item value;
    if (heap == NULL || heap->min == NULL) {
        return;
    }
    node = fib_node_search(heap->min, element);
    if (node == NULL) {
        return;
    }

    value = heap->min->data;
    fib_heap_decrease(heap, node, value - 1);
    fib_heap_pop(heap);
}

static void 
fib_node_destroy(fibonacci_node_pt node)
{
    fibonacci_node_pt pos;

    if (node == NULL) {
        return;
    }

    pos = node;
    do {
        fib_node_destroy(node->child);
        pos =  pos->right;
        free(pos);
    } while (pos != node);
}

void 
fib_heap_destroy(fibonacci_heap_pt heap)
{
    if (heap == NULL) {
        return;
    }
    fib_node_destroy(heap->min);
    free(heap->cons);
    free(heap);
}

static void 
fib_node_printnode(fibonacci_node_pt node, int h)
{
    int i;
    for (i=0; i < h; i++) {
        printf("    ");
    }
    if (node == NULL) {
        printf("*\n");
    }
    else {
        printf("%d\n", node->data);
    }
}

static void 
fib_node_print(fibonacci_node_pt node, int h)
{
    fibonacci_node_pt pos;
    if (node == NULL) {
        return;
    }

    pos = node;
    do {
        if (h == 0) {
            printf("---------------------------\n");
        }
        fib_node_printnode(pos, h);
        fib_node_print(pos->child, h + 1);
        pos = pos->right;
    } while (pos != node);
}

void 
fib_heap_print(fibonacci_heap_pt heap)
{
    fib_node_print(heap->min, 0);
}


/* 打印节点计数变量 */
static int node_num = 0;

static void 
export_dot(FILE *fp, fibonacci_node_pt node, char *last_label, char *tree_first_label)
{
    fibonacci_node_pt pos;

    /* 打印节点 */
    char node_name[10] = {0};
    if (node == NULL) {
        return;
    }
    sprintf(node_name, "n%d", node_num);
    if (last_label == NULL) {
        strcpy(tree_first_label, node_name);
    }

    fprintf(fp, "%s[label=%d, xlabel=%d];\n", node_name, node->data, node->marked);
    node_num++;

    if (last_label != NULL) {
        /* 打印边 */
        fprintf(fp, "%s->%s;\n", last_label, node_name);
        /* 打印子节点 */
        export_dot(fp, node->child, node_name, tree_first_label);
        /* 打印兄弟节点 */
        pos = node->right;
        while (pos != node) {
            sprintf(node_name, "n%d", node_num);
            fprintf(fp, "%s[label=%d, xlabel=%d];\n", node_name, pos->data, pos->marked);
            node_num++;
            fprintf(fp, "%s->%s;\n", last_label, node_name);
            //export_dot(fp, pos, last_label, tree_first_label);
            /* 打印子节点 */
            export_dot(fp, pos->child, node_name, tree_first_label);
            pos = pos->right;
        }
    }
    else {
        /* 打印子节点 */
        export_dot(fp, node->child, node_name, tree_first_label);
    }

}

void 
fib_heap_export_dot(fibonacci_heap_pt heap, char *filename, char *label)
{
    FILE *fp;
    fibonacci_node_pt tree;
    int cluster_num = 0;
    char tree_name[10] = {0};
    char last_tree_name[10] = {0};
    fp = fopen(filename, "w");
    fprintf(fp, "digraph g{\nnode[shape=circle];\nlabel=\"%s\";\nlabeljust=l;\nlabelloc=t;\n", label);
    tree = heap->min;
    do {
        fprintf(fp, "subgraph cluster_%d {\npencolor=green;label=\"树%d\";\n", cluster_num, cluster_num);
        strcpy(last_tree_name, tree_name);
        memset(tree_name, 0, sizeof(tree_name)/sizeof(char));
        export_dot(fp, tree, NULL, tree_name);
        cluster_num++; 
        fprintf(fp, "}\n");
        if (strlen(tree_name) > 0 && strlen(last_tree_name) > 0) {
            fprintf(fp, "%s->%s[constraint=false];\n", last_tree_name, tree_name);
        }
        tree = tree->right;
    } while (tree != heap->min);
    fprintf(fp, "}\n");
    fclose(fp);
}

fibonacci_heap.c

/* fibonacci_heap_test.c */
#include <stdlib.h>
#include <stdio.h>

#include "fibonacci_heap.h"

#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )

int
main(int argc, char *argv[])
{
    int a[] = {3, 52, 38, 41, 19, 30, 39, 18, 1};
    int b[] = {26, 35, 24, 46, 2};
    int c[] = {23, 7, 21};
    int i;
    int alen;
    int blen;
    int clen;
    int value;
    fibonacci_heap_pt ha = NULL, hb = NULL, hc = NULL;

    ha = fib_heap_new();
    hb = fib_heap_new();

    /* 以下测试代码主要创建一个ha的堆 */
    alen=LENGTH(a);
    printf("== 斐波那契堆(ha)中依次添加: ");
    for(i=0; i<alen; i++)
    {
        printf("%d ", a[i]);
        fib_heap_push(ha, a[i]);
    }
    printf("\n== 斐波那契堆(ha)的详细信息: \n");
    fib_heap_print(ha);
    fib_heap_pop(ha);
    printf("\n== 斐波那契堆(ha)的删除最小值后的详细信息: \n");
    fib_heap_print(ha);
    fib_heap_update(ha, 19, 17);

    /* 以下测试代码主要创建一个hb的堆 */
    alen=LENGTH(a);
    blen=LENGTH(b);
    printf("== 斐波那契堆(hb)中依次添加: ");
    for(i=0; i<blen; i++)
    {
        printf("%d ", b[i]);
        fib_heap_push(hb, b[i]);
    }
    fib_heap_pop(hb);

    clen=LENGTH(c);
    printf("== 斐波那契堆(hb)中依次添加: ");
    for(i=0; i<clen - 1; i++)
    {
        printf("%d ", c[i]);
        fib_heap_push(hb, c[i]);
    }
    fib_heap_push(hb, c[clen - 1]);
    printf("\n== 斐波那契堆(hb)的详细信息: \n");

    /* 以下合并两个堆，并生成一个跟"算法导论"中图解相似节点的树。^_^ 当然还是有些不一样 */
    alen=LENGTH(a);
    hc = fib_heap_union(ha, hb);
    printf("\n== 斐波那契堆(hc)的详细信息: \n");
    fib_heap_export_dot(hc, "union.dot", "合并结果");

    fib_heap_top(ha, &value);
    printf("\n== 斐波那契堆(ha)的最小值: %d\n", value);

    fib_heap_pop(hc);
    printf("\n== 斐波那契堆(ha)的删除最小值后的详细信息: \n");
    fib_heap_print(hc);
    fib_heap_export_dot(hc, "pop.dot", "删除最小值");

    fib_heap_update(hc, 23, 60);
    printf("\n== 斐波那契堆(hc)的修改节点23为60后的详细信息: \n");
    fib_heap_print(hc);
    fib_heap_export_dot(hc, "increase.dot", "增加数值");

    fib_heap_update(hc, 26, 20);
    fib_heap_update(hc, 35, 22);
    printf("\n== 斐波那契堆(hc)的修改节点35为22后的详细信息: \n");
    fib_heap_print(hc);
    fib_heap_export_dot(hc, "decrease.dot", "减少数值");

    fib_heap_destroy(ha);
    return 0;
}

fibonacci_heap_test.c

测试程序的运行结果

== 斐波那契堆(ha)中依次添加: 3 52 38 41 19 30 39 18 1 
== 斐波那契堆(ha)的详细信息: 
---------------------------
1
---------------------------
3
---------------------------
52
---------------------------
38
---------------------------
41
---------------------------
19
---------------------------
30
---------------------------
39
---------------------------
18

== 斐波那契堆(ha)的删除最小值后的详细信息: 
---------------------------
3
    18
        19
            30
        39
    38
        41
    52
== 斐波那契堆(hb)中依次添加: 26 35 24 46 2 == 斐波那契堆(hb)中依次添加: 23 7 
== 斐波那契堆(hb)的详细信息:

== 斐波那契堆(hc)的详细信息:

== 斐波那契堆(ha)的最小值: 3

== 斐波那契堆(ha)的删除最小值后的详细信息: 
---------------------------
7
    23
        52
    21
---------------------------
17
    30
---------------------------
18
    24
        35
            46
        26
    38
        41
    39

== 斐波那契堆(hc)的修改节点23为60后的详细信息: 
---------------------------
7
    21
---------------------------
52
---------------------------
17
    30
---------------------------
18
    24
        35
            46
        26
    38
        41
    39
---------------------------
60

== 斐波那契堆(hc)的修改节点35为22后的详细信息: 
---------------------------
7
    21
---------------------------
52
---------------------------
17
    30
---------------------------
18
    38
        41
    39
---------------------------
60
---------------------------
20
---------------------------
22
    46
---------------------------
24