• 斐波那契堆(二)之 C++的实现


    概要

    上一章介绍了斐波那契堆的基本概念,并通过C语言实现了斐波那契堆。本章是斐波那契堆的C++实现。

    目录
    1. 斐波那契堆的介绍
    2. 斐波那契堆的基本操作
    3. 斐波那契堆的C++实现(完整源码)
    4. 斐波那契堆的C++测试程序

    转载请注明出处:http://www.cnblogs.com/skywang12345/p/3659069.html


    更多内容:数据结构与算法系列 目录

    (01) 斐波那契堆(一)之 图文解析 和 C语言的实现 
    (02) 斐波那契堆(二)之 C++的实现 
    (03) 斐波那契堆(三)之 Java的实现

     

    斐波那契堆的介绍

    斐波那契堆(Fibonacci heap)是一种可合并堆,可用于实现合并优先队列。它比二项堆具有更好的平摊分析性能,它的合并操作的时间复杂度是O(1)。
    与二项堆一样,它也是由一组堆最小有序树组成,并且是一种可合并堆。
    与二项堆不同的是,斐波那契堆中的树不一定是二项树;而且二项堆中的树是有序排列的,但是斐波那契堆中的树都是有根而无序的。

     

    斐波那契堆的基本操作

    1. 基本定义

    template <class T>
    class FibNode {
        public:
            T key;                // 关键字(键值)
            int degree;            // 度数
            FibNode<T> *left;    // 左兄弟
            FibNode<T> *right;    // 右兄弟
            FibNode<T> *child;    // 第一个孩子节点
            FibNode<T> *parent;    // 父节点
            bool marked;        // 是否被删除第一个孩子
    
            FibNode(T value):key(value), degree(0), marked(false), 
                left(NULL),right(NULL),child(NULL),parent(NULL) {
                key    = value;
                degree = 0;
                marked = false;
                left   = this;
                right  = this;
                parent = NULL;
                child  = NULL;
            }
    };

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

    template <class T>
    class FibHeap {
        private:
            int keyNum;         // 堆中节点的总数
            int maxDegree;      // 最大度
            FibNode<T> *min;    // 最小节点(某个最小堆的根节点)
            FibNode<T> **cons;    // 最大度的内存区域
    
        public:
            FibHeap();
            ~FibHeap();
    
            // 新建key对应的节点,并将其插入到斐波那契堆中
            void insert(T key);
            // 移除斐波那契堆中的最小节点
            void removeMin();
            // 将other合并到当前堆中
            void combine(FibHeap<T> *other);
            // 获取斐波那契堆中最小键值,并保存到pkey中;成功返回true,否则返回false。
            bool minimum(T *pkey);
            // 将斐波那契堆中键值oldkey更新为newkey
            void update(T oldkey, T newkey);
            // 删除键值为key的节点
            void remove(T key);
            // 斐波那契堆中是否包含键值key
            bool contains(T key);
            // 打印斐波那契堆
            void print();
            // 销毁
            void destroy();
    
        private:
            // 将node从双链表移除
            void removeNode(FibNode<T> *node);
            // 将node堆结点加入root结点之前(循环链表中)
            void addNode(FibNode<T> *node, FibNode<T> *root);
            // 将双向链表b链接到双向链表a的后面
            void catList(FibNode<T> *a, FibNode<T> *b);
            // 将节点node插入到斐波那契堆中
            void insert(FibNode<T> *node);
            // 将"堆的最小结点"从根链表中移除,
            FibNode<T>* extractMin();
            // 将node链接到root根结点
            void link(FibNode<T>* node, FibNode<T>* root);
            // 创建consolidate所需空间
            void makeCons();
            // 合并斐波那契堆的根链表中左右相同度数的树
            void consolidate();
            // 修改度数
            void renewDegree(FibNode<T> *parent, int degree);
            // 将node从父节点parent的子链接中剥离出来,并使node成为"堆的根链表"中的一员。
            void cut(FibNode<T> *node, FibNode<T> *parent);
            // 对节点node进行"级联剪切"
            void cascadingCut(FibNode<T> *node) ;
            // 将斐波那契堆中节点node的值减少为key
            void decrease(FibNode<T> *node, T key);
            // 将斐波那契堆中节点node的值增加为key
            void increase(FibNode<T> *node, T key);
            // 更新斐波那契堆的节点node的键值为key
            void update(FibNode<T> *node, T key);
            // 在最小堆root中查找键值为key的节点
            FibNode<T>* search(FibNode<T> *root, T key);
            // 在斐波那契堆中查找键值为key的节点
            FibNode<T>* search(T key);
            // 删除结点node
            void remove(FibNode<T> *node);
            // 销毁斐波那契堆
            void destroyNode(FibNode<T> *node);
            // 打印"斐波那契堆"
            void print(FibNode<T> *node, FibNode<T> *prev, int direction);
    };

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

    从中可以看出,斐波那契堆是由一组最小堆组成,这些最小堆的根节点组成了双向链表(后文称为"根链表");斐波那契堆中的最小节点就是"根链表中的最小节点"!

    PS. 上面这幅图的结构和测试代码中的"基本信息"测试函数的结果是一致的;你可以通过测试程序来亲自验证!

     

    2. 插入操作

    插入操作非常简单:插入一个节点到堆中,直接将该节点插入到"根链表的min节点"之前即可;若被插入节点比"min节点"小,则更新"min节点"为被插入节点。

    上面是插入操作的示意图。

    斐波那契堆的根链表是"双向链表",这里将min节点看作双向联表的表头(后文也是如此)。在插入节点时,每次都是"将节点插入到min节点之前(即插入到双链表末尾)"。此外,对于根链表中最小堆都只有一个节点的情况,插入操作就很演化成双向链表的插入操作。

    此外,插入操作示意图与测试程序中的"插入操作"相对应,感兴趣的可以亲自验证。

    插入操作代码

    /*
     * 将node堆结点加入root结点之前(循环链表中)
     *   a …… root
     *   a …… node …… root
    */
    template <class T>
    void FibHeap<T>::addNode(FibNode<T> *node, FibNode<T> *root)
    {
        node->left        = root->left;
        root->left->right = node;
        node->right       = root;
        root->left        = node;
    }
     
    /*
     * 将节点node插入到斐波那契堆中
     */
    template <class T>
    void FibHeap<T>::insert(FibNode<T> *node)
    {
        if (keyNum == 0)
            min = node;
        else
           {
            addNode(node, min);
            if (node->key < min->key)
                min = node;
        }
        keyNum++;
    }

    3. 合并操作

    合并操作和插入操作的原理非常类似:将一个堆的根链表插入到另一个堆的根链表上即可。简单来说,就是将两个双链表拼接成一个双向链表。

    上面是合并操作的示意图。该操作示意图与测试程序中的"合并操作"相对应!

    合并操作代码

    /*
     * 将双向链表b链接到双向链表a的后面
     *
     * 注意: 此处a和b都是双向链表
     */
    template <class T>
    void FibHeap<T>::catList(FibNode<T> *a, FibNode<T> *b)
    {
        FibNode<T> *tmp;
    
        tmp            = a->right;
        a->right       = b->right;
        b->right->left = a;
        b->right       = tmp;
        tmp->left      = b;
    }
    
      
    /*
     * 将other合并到当前堆中
     */
    template <class T>
    void FibHeap<T>::combine(FibHeap<T> *other)
    {
        if (other==NULL)
            return ;
    
        if(other->maxDegree > this->maxDegree)
            swap(*this, *other);
    
        if((this->min) == NULL)                // this无"最小节点"
        {
            this->min = other->min;
            this->keyNum = other->keyNum;
            free(other->cons);
            delete other;
        }
        else if((other->min) == NULL)           // this有"最小节点" && other无"最小节点"
        {
            free(other->cons);
            delete other;
        }                                       // this有"最小节点" && other有"最小节点"
        else
        {
            // 将"other中根链表"添加到"this"中
            catList(this->min, other->min);
    
            if (this->min->key > other->min->key)
                this->min = other->min;
            this->keyNum += other->keyNum;
            free(other->cons);
            delete other;
        }
    }

    4. 取出最小节点

    抽取最小结点的操作是斐波那契堆中较复杂的操作。
    (1)将要抽取最小结点的子树都直接串联在根表中;
    (2)合并所有degree相等的树,直到没有相等的degree的树。

    上面是取出最小节点的示意图。图中应该写的非常明白了,若有疑问,看代码。

    此外,该操作示意图与测试程序中的"删除最小节点"相对应!有兴趣的可以亲自验证。

    取出最小节点代码

    /*
     * 将"堆的最小结点"从根链表中移除,
     * 这意味着"将最小节点所属的树"从堆中移除!
     */
    template <class T>
    FibNode<T>* FibHeap<T>::extractMin()
    {
        FibNode<T> *p = min;
    
        if (p == p->right)
            min = NULL;
        else
        {
            removeNode(p);
            min = p->right;
        }
        p->left = p->right = p;
    
        return p;
    }
     
    /*
     * 将node链接到root根结点
     */
    template <class T>
    void FibHeap<T>::link(FibNode<T>* node, FibNode<T>* root)
    {
        // 将node从双链表中移除
        removeNode(node);
        // 将node设为root的孩子
        if (root->child == NULL)
            root->child = node;
        else
            addNode(node, root->child);
    
        node->parent = root;
        root->degree++;
        node->marked = false;
    }
     
    /* 
     * 创建consolidate所需空间
     */
    template <class T>
    void FibHeap<T>::makeCons()
    {
        int old = maxDegree;
    
        // 计算log2(keyNum),"+1"意味着向上取整!
        // ex. log2(13) = 3,向上取整为3+1=4。
        maxDegree = (log(keyNum)/log(2.0)) + 1;
        if (old >= maxDegree)
            return ;
    
        // 因为度为maxDegree可能被合并,所以要maxDegree+1
        cons = (FibNode<T> **)realloc(cons, 
                sizeof(FibHeap<T> *) * (maxDegree + 1));
    }
    
    /* 
     * 合并斐波那契堆的根链表中左右相同度数的树
     */
    template <class T>
    void FibHeap<T>::consolidate()
    {
        int i, d, D;
        FibNode<T> *x, *y, *tmp;
    
        makeCons();//开辟哈希所用空间
        D = maxDegree + 1;
    
        for (i = 0; i < D; i++)
            cons[i] = NULL;
     
        // 合并相同度的根节点,使每个度数的树唯一
        while (min != NULL)
        {
            x = extractMin();                // 取出堆中的最小树(最小节点所在的树)
            d = x->degree;                    // 获取最小树的度数
            // cons[d] != NULL,意味着有两棵树(x和y)的"度数"相同。
            while (cons[d] != NULL)
            {
                y = cons[d];                // y是"与x的度数相同的树" 
                if (x->key > y->key)        // 保证x的键值比y小
                    swap(x, y);
    
                link(y, x);    // 将y链接到x中
                cons[d] = NULL;
                d++;
            }
            cons[d] = x;
        }
        min = NULL;
     
        // 将cons中的结点重新加到根表中
        for (i=0; i<D; i++)
        {
            if (cons[i] != NULL)
            {
                if (min == NULL)
                    min = cons[i];
                else
                {
                    addNode(cons[i], min);
                    if ((cons[i])->key < min->key)
                        min = cons[i];
                }
            }
        }
    }
     
    /*
     * 移除最小节点
     */
    template <class T>
    void FibHeap<T>::removeMin()
    {
        if (min==NULL)
            return ;
    
        FibNode<T> *child = NULL;
        FibNode<T> *m = min;
        // 将min每一个儿子(儿子和儿子的兄弟)都添加到"斐波那契堆的根链表"中
        while (m->child != NULL)
        {
            child = m->child;
            removeNode(child);
            if (child->right == child)
                m->child = NULL;
            else
                m->child = child->right;
    
            addNode(child, min);
            child->parent = NULL;
        }
    
        // 将m从根链表中移除
        removeNode(m);
        // 若m是堆中唯一节点,则设置堆的最小节点为NULL;
        // 否则,设置堆的最小节点为一个非空节点(m->right),然后再进行调节。
        if (m->right == m)
            min = NULL;
        else
        {
            min = m->right;
            consolidate();
        }
        keyNum--;
    
        delete m;
    }

     

    5. 减小节点值

    减少斐波那契堆中的节点的键值,这个操作的难点是:如果减少节点后破坏了"最小堆"性质,如何去维护呢?下面对一般性情况进行分析。
    (1) 首先,将"被减小节点"从"它所在的最小堆"剥离出来;然后将"该节点"关联到"根链表"中。 倘若被减小的节点不是单独一个节点,而是包含子树的树根。则是将以"被减小节点"为根的子树从"最小堆"中剥离出来,然后将该树关联到根链表中。
    (2) 接着,对"被减少节点"的原父节点进行"级联剪切"。所谓"级联剪切",就是在被减小节点破坏了最小堆性质,并被切下来之后;再从"它的父节点"进行递归级联剪切操作。
          而级联操作的具体动作则是:若父节点(被减小节点的父节点)的marked标记为false,则将其设为true,然后退出。
                                                              否则,将父节点从最小堆中切下来(方式和"切被减小节点的方式"一样);然后递归对祖父节点进行"级联剪切"。
          marked标记的作用就是用来标记"该节点的子节点是否有被删除过",它的作用是来实现级联剪切。而级联剪切的真正目的是为了防止"最小堆"由二叉树演化成链表。
    (3) 最后,别忘了对根链表的最小节点进行更新。

    上面是减小节点值的示意图。该操作示意图与测试程序中的"减小节点"相对应!

    减小节点值的代码

    /* 
     * 修改度数
     */
    template <class T>
    void FibHeap<T>::renewDegree(FibNode<T> *parent, int degree)
    {
        parent->degree -= degree;
        if (parent-> parent != NULL)
            renewDegree(parent->parent, degree);
    }
     
    /* 
     * 将node从父节点parent的子链接中剥离出来,
     * 并使node成为"堆的根链表"中的一员。
     */
    template <class T>
    void FibHeap<T>::cut(FibNode<T> *node, FibNode<T> *parent)
    {
        removeNode(node);
        renewDegree(parent, node->degree);
        // node没有兄弟
        if (node == node->right) 
            parent->child = NULL;
        else 
            parent->child = node->right;
    
        node->parent = NULL;
        node->left = node->right = node;
        node->marked = false;
        // 将"node所在树"添加到"根链表"中
        addNode(node, min);
    }
    
    /* 
     * 对节点node进行"级联剪切"
     *
     * 级联剪切:如果减小后的结点破坏了最小堆性质,
     *     则把它切下来(即从所在双向链表中删除,并将
     *     其插入到由最小树根节点形成的双向链表中),
     *     然后再从"被切节点的父节点"到所在树根节点递归执行级联剪枝
     */
    template <class T>
    void FibHeap<T>::cascadingCut(FibNode<T> *node) 
    {
        FibNode<T> *parent = node->parent;
        if (parent != NULL)
        {
            if (node->marked == false) 
                node->marked = true;
            else
            {
                cut(node, parent);
                cascadingCut(parent);
            }
        }
    }
    
    /* 
     * 将斐波那契堆中节点node的值减少为key
     */
    template <class T>
    void FibHeap<T>::decrease(FibNode<T> *node, T key)
    {
        FibNode<T> *parent;
    
        if (min==NULL ||node==NULL) 
            return ;
    
        if ( key>=node->key)
        {
            cout << "decrease failed: the new key(" << key <<") "
                 << "is no smaller than current key(" << node->key <<")" << endl;
            return ;
        }
    
        node->key = key;
        parent = node->parent;
        if (parent!=NULL && node->key < parent->key)
        {
            // 将node从父节点parent中剥离出来,并将node添加到根链表中
            cut(node, parent);
            cascadingCut(parent);
        }
    
        // 更新最小节点
        if (node->key < min->key)
            min = node;
    }

    6. 增加节点值

    增加节点值和减少节点值类似,这个操作的难点也是如何维护"最小堆"性质。思路如下:
    (1) 将"被增加节点"的"左孩子和左孩子的所有兄弟"都链接到根链表中。
    (2) 接下来,把"被增加节点"添加到根链表;但是别忘了对其进行级联剪切。

    上面是增加节点值的示意图。该操作示意图与测试程序中的"增大节点"相对应!

    增加节点值的代码

    /* 
     * 将斐波那契堆中节点node的值增加为key
     */
    template <class T>
    void FibHeap<T>::increase(FibNode<T> *node, T key)
    {
        FibNode<T> *child, *parent, *right;
    
        if (min==NULL ||node==NULL) 
            return ;
    
        if (key <= node->key)
        {
            cout << "increase failed: the new key(" << key <<") " 
                 << "is no greater than current key(" << node->key <<")" << endl;
            return ;
        }
    
        // 将node每一个儿子(不包括孙子,重孙,...)都添加到"斐波那契堆的根链表"中
        while (node->child != NULL)
        {
            child = node->child;
            removeNode(child);               // 将child从node的子链表中删除
            if (child->right == child)
                node->child = NULL;
            else
                node->child = child->right;
    
            addNode(child, min);       // 将child添加到根链表中
            child->parent = NULL;
        }
        node->degree = 0;
        node->key = key;
    
        // 如果node不在根链表中,
        //     则将node从父节点parent的子链接中剥离出来,
        //     并使node成为"堆的根链表"中的一员,
        //     然后进行"级联剪切"
        // 否则,则判断是否需要更新堆的最小节点
        parent = node->parent;
        if(parent != NULL)
        {
            cut(node, parent);
            cascadingCut(parent);
        }
        else if(min == node)
        {
            right = node->right;
            while(right != node)
            {
                if(node->key > right->key)
                    min = right;
                right = right->right;
            }
        }
    }

    7. 删除节点

    删除节点,本文采用了操作是:"取出最小节点"和"减小节点值"的组合。
    (1) 先将被删除节点的键值减少。减少后的值要比"原最小节点的值"即可。
    (2) 接着,取出最小节点即可。

    删除节点值的代码

    /*
     * 删除结点node
     */
    template <class T>
    void FibHeap<T>::remove(FibNode<T> *node)
    {
        T m = min->key-1;
        decrease(node, m-1);
        removeMin();
    }


    注意:关于斐波那契堆的"更新"、"打印"、"销毁"等接口就不再单独介绍了。后文的源码中有给出它们的实现代码,Please RTFSC(Read The Fucking Source Code)!

     

    斐波那契堆的C++实现(完整源码)

    斐波那契堆的实现文件(FibHeap.cpp)

      1 /**
      2  * C++: 斐波那契堆
      3  *
      4  * @author skywang
      5  * @date 2014/04/06
      6  */
      7 
      8 #ifndef _FIBONACCI_TREE_HPP_
      9 #define _FIBONACCI_TREE_HPP_
     10 
     11 #include <iomanip>
     12 #include <iostream>
     13 #include <cstdlib>
     14 #include <cmath>
     15 using namespace std;
     16 
     17 template <class T>
     18 class FibNode {
     19     public:
     20         T key;                // 关键字(键值)
     21         int degree;            // 度数
     22         FibNode<T> *left;    // 左兄弟
     23         FibNode<T> *right;    // 右兄弟
     24         FibNode<T> *child;    // 第一个孩子节点
     25         FibNode<T> *parent;    // 父节点
     26         bool marked;        // 是否被删除第一个孩子
     27 
     28         FibNode(T value):key(value), degree(0), marked(false), 
     29             left(NULL),right(NULL),child(NULL),parent(NULL) {
     30             key    = value;
     31             degree = 0;
     32             marked = false;
     33             left   = this;
     34             right  = this;
     35             parent = NULL;
     36             child  = NULL;
     37         }
     38 };
     39 
     40 template <class T>
     41 class FibHeap {
     42     private:
     43         int keyNum;         // 堆中节点的总数
     44         int maxDegree;      // 最大度
     45         FibNode<T> *min;    // 最小节点(某个最小堆的根节点)
     46         FibNode<T> **cons;    // 最大度的内存区域
     47 
     48     public:
     49         FibHeap();
     50         ~FibHeap();
     51 
     52         // 新建key对应的节点,并将其插入到斐波那契堆中
     53         void insert(T key);
     54         // 移除斐波那契堆中的最小节点
     55         void removeMin();
     56         // 将other合并到当前堆中
     57         void combine(FibHeap<T> *other);
     58         // 获取斐波那契堆中最小键值,并保存到pkey中;成功返回true,否则返回false。
     59         bool minimum(T *pkey);
     60         // 将斐波那契堆中键值oldkey更新为newkey
     61         void update(T oldkey, T newkey);
     62         // 删除键值为key的节点
     63         void remove(T key);
     64         // 斐波那契堆中是否包含键值key
     65         bool contains(T key);
     66         // 打印斐波那契堆
     67         void print();
     68         // 销毁
     69         void destroy();
     70 
     71     private:
     72         // 将node从双链表移除
     73         void removeNode(FibNode<T> *node);
     74         // 将node堆结点加入root结点之前(循环链表中)
     75         void addNode(FibNode<T> *node, FibNode<T> *root);
     76         // 将双向链表b链接到双向链表a的后面
     77         void catList(FibNode<T> *a, FibNode<T> *b);
     78         // 将节点node插入到斐波那契堆中
     79         void insert(FibNode<T> *node);
     80         // 将"堆的最小结点"从根链表中移除,
     81         FibNode<T>* extractMin();
     82         // 将node链接到root根结点
     83         void link(FibNode<T>* node, FibNode<T>* root);
     84         // 创建consolidate所需空间
     85         void makeCons();
     86         // 合并斐波那契堆的根链表中左右相同度数的树
     87         void consolidate();
     88         // 修改度数
     89         void renewDegree(FibNode<T> *parent, int degree);
     90         // 将node从父节点parent的子链接中剥离出来,并使node成为"堆的根链表"中的一员。
     91         void cut(FibNode<T> *node, FibNode<T> *parent);
     92         // 对节点node进行"级联剪切"
     93         void cascadingCut(FibNode<T> *node) ;
     94         // 将斐波那契堆中节点node的值减少为key
     95         void decrease(FibNode<T> *node, T key);
     96         // 将斐波那契堆中节点node的值增加为key
     97         void increase(FibNode<T> *node, T key);
     98         // 更新斐波那契堆的节点node的键值为key
     99         void update(FibNode<T> *node, T key);
    100         // 在最小堆root中查找键值为key的节点
    101         FibNode<T>* search(FibNode<T> *root, T key);
    102         // 在斐波那契堆中查找键值为key的节点
    103         FibNode<T>* search(T key);
    104         // 删除结点node
    105         void remove(FibNode<T> *node);
    106         // 销毁斐波那契堆
    107         void destroyNode(FibNode<T> *node);
    108         // 打印"斐波那契堆"
    109         void print(FibNode<T> *node, FibNode<T> *prev, int direction);
    110 };
    111 
    112 /* 
    113  * 构造函数
    114  */
    115 template <class T>
    116 FibHeap<T>::FibHeap()
    117 {
    118     keyNum = 0;
    119     maxDegree = 0;
    120     min = NULL;
    121     cons = NULL;
    122 }
    123 
    124 /* 
    125  * 析构函数
    126  */
    127 template <class T>
    128 FibHeap<T>::~FibHeap() 
    129 {
    130 }
    131 
    132 /* 
    133  * 将node从双链表移除
    134  */
    135 template <class T>
    136 void FibHeap<T>::removeNode(FibNode<T> *node)
    137 {
    138     node->left->right = node->right;
    139     node->right->left = node->left;
    140 }
    141  
    142 /*
    143  * 将node堆结点加入root结点之前(循环链表中)
    144  *   a …… root
    145  *   a …… node …… root
    146 */
    147 template <class T>
    148 void FibHeap<T>::addNode(FibNode<T> *node, FibNode<T> *root)
    149 {
    150     node->left        = root->left;
    151     root->left->right = node;
    152     node->right       = root;
    153     root->left        = node;
    154 }
    155  
    156 /*
    157  * 将节点node插入到斐波那契堆中
    158  */
    159 template <class T>
    160 void FibHeap<T>::insert(FibNode<T> *node)
    161 {
    162     if (keyNum == 0)
    163         min = node;
    164     else
    165        {
    166         addNode(node, min);
    167         if (node->key < min->key)
    168             min = node;
    169     }
    170     keyNum++;
    171 }
    172  
    173 /* 
    174  * 新建键值为key的节点,并将其插入到斐波那契堆中
    175  */
    176 template <class T>
    177 void FibHeap<T>::insert(T key)
    178 {
    179     FibNode<T> *node;
    180 
    181     node = new FibNode<T>(key);
    182     if (node == NULL)
    183         return ;
    184 
    185     insert(node);
    186 }
    187 
    188 /*
    189  * 将双向链表b链接到双向链表a的后面
    190  *
    191  * 注意: 此处a和b都是双向链表
    192  */
    193 template <class T>
    194 void FibHeap<T>::catList(FibNode<T> *a, FibNode<T> *b)
    195 {
    196     FibNode<T> *tmp;
    197 
    198     tmp            = a->right;
    199     a->right       = b->right;
    200     b->right->left = a;
    201     b->right       = tmp;
    202     tmp->left      = b;
    203 }
    204 
    205   
    206 /*
    207  * 将other合并到当前堆中
    208  */
    209 template <class T>
    210 void FibHeap<T>::combine(FibHeap<T> *other)
    211 {
    212     if (other==NULL)
    213         return ;
    214 
    215     if(other->maxDegree > this->maxDegree)
    216         swap(*this, *other);
    217 
    218     if((this->min) == NULL)                // this无"最小节点"
    219     {
    220         this->min = other->min;
    221         this->keyNum = other->keyNum;
    222         free(other->cons);
    223         delete other;
    224     }
    225     else if((other->min) == NULL)           // this有"最小节点" && other无"最小节点"
    226     {
    227         free(other->cons);
    228         delete other;
    229     }                                       // this有"最小节点" && other有"最小节点"
    230     else
    231     {
    232         // 将"other中根链表"添加到"this"中
    233         catList(this->min, other->min);
    234 
    235         if (this->min->key > other->min->key)
    236             this->min = other->min;
    237         this->keyNum += other->keyNum;
    238         free(other->cons);
    239         delete other;
    240     }
    241 }
    242 
    243 /*
    244  * 将"堆的最小结点"从根链表中移除,
    245  * 这意味着"将最小节点所属的树"从堆中移除!
    246  */
    247 template <class T>
    248 FibNode<T>* FibHeap<T>::extractMin()
    249 {
    250     FibNode<T> *p = min;
    251 
    252     if (p == p->right)
    253         min = NULL;
    254     else
    255     {
    256         removeNode(p);
    257         min = p->right;
    258     }
    259     p->left = p->right = p;
    260 
    261     return p;
    262 }
    263  
    264 /*
    265  * 将node链接到root根结点
    266  */
    267 template <class T>
    268 void FibHeap<T>::link(FibNode<T>* node, FibNode<T>* root)
    269 {
    270     // 将node从双链表中移除
    271     removeNode(node);
    272     // 将node设为root的孩子
    273     if (root->child == NULL)
    274         root->child = node;
    275     else
    276         addNode(node, root->child);
    277 
    278     node->parent = root;
    279     root->degree++;
    280     node->marked = false;
    281 }
    282  
    283 /* 
    284  * 创建consolidate所需空间
    285  */
    286 template <class T>
    287 void FibHeap<T>::makeCons()
    288 {
    289     int old = maxDegree;
    290 
    291     // 计算log2(keyNum),"+1"意味着向上取整!
    292     // ex. log2(13) = 3,向上取整为3+1=4。
    293     maxDegree = (log(keyNum)/log(2.0)) + 1;
    294     if (old >= maxDegree)
    295         return ;
    296 
    297     // 因为度为maxDegree可能被合并,所以要maxDegree+1
    298     cons = (FibNode<T> **)realloc(cons, 
    299             sizeof(FibHeap<T> *) * (maxDegree + 1));
    300 }
    301 
    302 /* 
    303  * 合并斐波那契堆的根链表中左右相同度数的树
    304  */
    305 template <class T>
    306 void FibHeap<T>::consolidate()
    307 {
    308     int i, d, D;
    309     FibNode<T> *x, *y, *tmp;
    310 
    311     makeCons();//开辟哈希所用空间
    312     D = maxDegree + 1;
    313 
    314     for (i = 0; i < D; i++)
    315         cons[i] = NULL;
    316  
    317     // 合并相同度的根节点,使每个度数的树唯一
    318     while (min != NULL)
    319     {
    320         x = extractMin();                // 取出堆中的最小树(最小节点所在的树)
    321         d = x->degree;                    // 获取最小树的度数
    322         // cons[d] != NULL,意味着有两棵树(x和y)的"度数"相同。
    323         while (cons[d] != NULL)
    324         {
    325             y = cons[d];                // y是"与x的度数相同的树" 
    326             if (x->key > y->key)        // 保证x的键值比y小
    327                 swap(x, y);
    328 
    329             link(y, x);    // 将y链接到x中
    330             cons[d] = NULL;
    331             d++;
    332         }
    333         cons[d] = x;
    334     }
    335     min = NULL;
    336  
    337     // 将cons中的结点重新加到根表中
    338     for (i=0; i<D; i++)
    339     {
    340         if (cons[i] != NULL)
    341         {
    342             if (min == NULL)
    343                 min = cons[i];
    344             else
    345             {
    346                 addNode(cons[i], min);
    347                 if ((cons[i])->key < min->key)
    348                     min = cons[i];
    349             }
    350         }
    351     }
    352 }
    353  
    354 /*
    355  * 移除最小节点
    356  */
    357 template <class T>
    358 void FibHeap<T>::removeMin()
    359 {
    360     if (min==NULL)
    361         return ;
    362 
    363     FibNode<T> *child = NULL;
    364     FibNode<T> *m = min;
    365     // 将min每一个儿子(儿子和儿子的兄弟)都添加到"斐波那契堆的根链表"中
    366     while (m->child != NULL)
    367     {
    368         child = m->child;
    369         removeNode(child);
    370         if (child->right == child)
    371             m->child = NULL;
    372         else
    373             m->child = child->right;
    374 
    375         addNode(child, min);
    376         child->parent = NULL;
    377     }
    378 
    379     // 将m从根链表中移除
    380     removeNode(m);
    381     // 若m是堆中唯一节点,则设置堆的最小节点为NULL;
    382     // 否则,设置堆的最小节点为一个非空节点(m->right),然后再进行调节。
    383     if (m->right == m)
    384         min = NULL;
    385     else
    386     {
    387         min = m->right;
    388         consolidate();
    389     }
    390     keyNum--;
    391 
    392     delete m;
    393 }
    394 
    395 /*
    396  * 获取斐波那契堆中最小键值,并保存到pkey中;成功返回true,否则返回false。
    397  */
    398 template <class T>
    399 bool FibHeap<T>::minimum(T *pkey)
    400 {
    401     if (min==NULL || pkey==NULL)
    402         return false;
    403 
    404     *pkey = min->key;
    405     return true;
    406 }
    407   
    408 /* 
    409  * 修改度数
    410  */
    411 template <class T>
    412 void FibHeap<T>::renewDegree(FibNode<T> *parent, int degree)
    413 {
    414     parent->degree -= degree;
    415     if (parent-> parent != NULL)
    416         renewDegree(parent->parent, degree);
    417 }
    418  
    419 /* 
    420  * 将node从父节点parent的子链接中剥离出来,
    421  * 并使node成为"堆的根链表"中的一员。
    422  */
    423 template <class T>
    424 void FibHeap<T>::cut(FibNode<T> *node, FibNode<T> *parent)
    425 {
    426     removeNode(node);
    427     renewDegree(parent, node->degree);
    428     // node没有兄弟
    429     if (node == node->right) 
    430         parent->child = NULL;
    431     else 
    432         parent->child = node->right;
    433 
    434     node->parent = NULL;
    435     node->left = node->right = node;
    436     node->marked = false;
    437     // 将"node所在树"添加到"根链表"中
    438     addNode(node, min);
    439 }
    440 
    441 /* 
    442  * 对节点node进行"级联剪切"
    443  *
    444  * 级联剪切:如果减小后的结点破坏了最小堆性质,
    445  *     则把它切下来(即从所在双向链表中删除,并将
    446  *     其插入到由最小树根节点形成的双向链表中),
    447  *     然后再从"被切节点的父节点"到所在树根节点递归执行级联剪枝
    448  */
    449 template <class T>
    450 void FibHeap<T>::cascadingCut(FibNode<T> *node) 
    451 {
    452     FibNode<T> *parent = node->parent;
    453     if (parent != NULL)
    454     {
    455         if (node->marked == false) 
    456             node->marked = true;
    457         else
    458         {
    459             cut(node, parent);
    460             cascadingCut(parent);
    461         }
    462     }
    463 }
    464 
    465 /* 
    466  * 将斐波那契堆中节点node的值减少为key
    467  */
    468 template <class T>
    469 void FibHeap<T>::decrease(FibNode<T> *node, T key)
    470 {
    471     FibNode<T> *parent;
    472 
    473     if (min==NULL ||node==NULL) 
    474         return ;
    475 
    476     if ( key>=node->key)
    477     {
    478         cout << "decrease failed: the new key(" << key <<") "
    479              << "is no smaller than current key(" << node->key <<")" << endl;
    480         return ;
    481     }
    482 
    483     node->key = key;
    484     parent = node->parent;
    485     if (parent!=NULL && node->key < parent->key)
    486     {
    487         // 将node从父节点parent中剥离出来,并将node添加到根链表中
    488         cut(node, parent);
    489         cascadingCut(parent);
    490     }
    491 
    492     // 更新最小节点
    493     if (node->key < min->key)
    494         min = node;
    495 }
    496 
    497 /* 
    498  * 将斐波那契堆中节点node的值增加为key
    499  */
    500 template <class T>
    501 void FibHeap<T>::increase(FibNode<T> *node, T key)
    502 {
    503     FibNode<T> *child, *parent, *right;
    504 
    505     if (min==NULL ||node==NULL) 
    506         return ;
    507 
    508     if (key <= node->key)
    509     {
    510         cout << "increase failed: the new key(" << key <<") " 
    511              << "is no greater than current key(" << node->key <<")" << endl;
    512         return ;
    513     }
    514 
    515     // 将node每一个儿子(不包括孙子,重孙,...)都添加到"斐波那契堆的根链表"中
    516     while (node->child != NULL)
    517     {
    518         child = node->child;
    519         removeNode(child);               // 将child从node的子链表中删除
    520         if (child->right == child)
    521             node->child = NULL;
    522         else
    523             node->child = child->right;
    524 
    525         addNode(child, min);       // 将child添加到根链表中
    526         child->parent = NULL;
    527     }
    528     node->degree = 0;
    529     node->key = key;
    530 
    531     // 如果node不在根链表中,
    532     //     则将node从父节点parent的子链接中剥离出来,
    533     //     并使node成为"堆的根链表"中的一员,
    534     //     然后进行"级联剪切"
    535     // 否则,则判断是否需要更新堆的最小节点
    536     parent = node->parent;
    537     if(parent != NULL)
    538     {
    539         cut(node, parent);
    540         cascadingCut(parent);
    541     }
    542     else if(min == node)
    543     {
    544         right = node->right;
    545         while(right != node)
    546         {
    547             if(node->key > right->key)
    548                 min = right;
    549             right = right->right;
    550         }
    551     }
    552 }
    553 
    554 /* 
    555  * 更新斐波那契堆的节点node的键值为key
    556  */
    557 template <class T>
    558 void FibHeap<T>::update(FibNode<T> *node, T key)
    559 {
    560     if(key < node->key)
    561         decrease(node, key);
    562     else if(key > node->key)
    563         increase(node, key);
    564     else
    565         cout << "No need to update!!!" << endl;
    566 }
    567   
    568 template <class T>
    569 void FibHeap<T>::update(T oldkey, T newkey)
    570 {
    571     FibNode<T> *node;
    572 
    573     node = search(oldkey);
    574     if (node!=NULL)
    575         update(node, newkey);
    576 }
    577 
    578 /*
    579  * 在最小堆root中查找键值为key的节点
    580  */
    581 template <class T>
    582 FibNode<T>* FibHeap<T>::search(FibNode<T> *root, T key)
    583 {
    584     FibNode<T> *t = root;    // 临时节点
    585     FibNode<T> *p = NULL;    // 要查找的节点
    586 
    587     if (root==NULL)
    588         return root;
    589 
    590     do
    591     {
    592         if (t->key == key)
    593         {
    594             p = t;
    595             break;
    596         } 
    597         else
    598         {
    599             if ((p = search(t->child, key)) != NULL) 
    600                 break;
    601         }    
    602         t = t->right;
    603     } while (t != root);
    604 
    605     return p;
    606 }
    607  
    608 /*
    609  * 在斐波那契堆中查找键值为key的节点
    610  */
    611 template <class T>
    612 FibNode<T>* FibHeap<T>::search(T key)
    613 {
    614     if (min==NULL)
    615         return NULL;
    616 
    617     return search(min, key);
    618 }
    619 
    620 /*
    621  * 在斐波那契堆中是否存在键值为key的节点。
    622  * 存在返回true,否则返回false。
    623  */
    624 template <class T>
    625 bool FibHeap<T>::contains(T key)
    626 {
    627     return search(key)!=NULL ? true: false;
    628 }
    629 
    630 /*
    631  * 删除结点node
    632  */
    633 template <class T>
    634 void FibHeap<T>::remove(FibNode<T> *node)
    635 {
    636     T m = min->key-1;
    637     decrease(node, m-1);
    638     removeMin();
    639 }
    640 
    641 template <class T>
    642 void FibHeap<T>::remove(T key)
    643 {
    644     FibNode<T> *node;
    645 
    646     if (min==NULL)
    647         return ;
    648 
    649     node = search(key);
    650     if (node==NULL)
    651         return ;
    652 
    653     remove(node);
    654 }
    655  
    656 /* 
    657  * 销毁斐波那契堆
    658  */
    659 template <class T>
    660 void FibHeap<T>::destroyNode(FibNode<T> *node)
    661 {
    662     FibNode<T> *start = node;
    663 
    664     if(node == NULL)
    665         return;
    666 
    667     do {
    668         destroyNode(node->child);
    669         // 销毁node,并将node指向下一个
    670         node = node->right;
    671         delete node->left;
    672     } while(node != start);
    673 }
    674  
    675 template <class T>
    676 void FibHeap<T>::destroy()
    677 {
    678     destroyNode(min);
    679     free(cons);
    680 }
    681 
    682 /*
    683  * 打印"斐波那契堆"
    684  *
    685  * 参数说明:
    686  *     node       -- 当前节点
    687  *     prev       -- 当前节点的前一个节点(父节点or兄弟节点)
    688  *     direction  --  1,表示当前节点是一个左孩子;
    689  *                    2,表示当前节点是一个兄弟节点。
    690  */
    691 template <class T>
    692 void FibHeap<T>::print(FibNode<T> *node, FibNode<T> *prev, int direction)
    693 {
    694     FibNode<T> *start=node;
    695 
    696     if (node==NULL)
    697         return ;
    698     do
    699     {
    700         if (direction == 1)
    701             cout << setw(8) << node->key << "(" << node->degree << ") is "<< setw(2) << prev->key << "'s child" << endl;
    702         else
    703             cout << setw(8) << node->key << "(" << node->degree << ") is "<< setw(2) << prev->key << "'s next" << endl;
    704 
    705         if (node->child != NULL)
    706             print(node->child, node, 1);
    707 
    708         // 兄弟节点
    709         prev = node;
    710         node = node->right;
    711         direction = 2;
    712     } while(node != start);
    713 }
    714 
    715 template <class T>
    716 void FibHeap<T>::print()
    717 {
    718     int i=0;
    719     FibNode<T> *p;
    720 
    721     if (min==NULL)
    722         return ;
    723 
    724     cout << "== 斐波那契堆的详细信息: ==" << endl;
    725     p = min;
    726     do {
    727         i++;
    728         cout << setw(2) << i << ". " << setw(4) << p->key << "(" << p->degree << ") is root" << endl;
    729 
    730         print(p->child, p, 1);
    731         p = p->right;
    732     } while (p != min);
    733     cout << endl;
    734 }
    735 
    736 #endif
    View Code

    斐波那契堆的测试程序(Main.cpp)

      1 /**
      2  * C 语言: 斐波那契堆
      3  *
      4  * @author skywang
      5  * @date 2014/04/06
      6  */
      7 
      8 #include <iostream>
      9 #include "FibHeap.h"
     10 using namespace std;
     11 
     12 #define DEBUG 0
     13 
     14 // 共8个
     15 int a[] = {12,  7, 25, 15, 28, 
     16            33, 41,  1};
     17 // 共14个
     18 int b[] = {18, 35, 20, 42,  9, 
     19            31, 23,  6, 48, 11, 
     20            24, 52, 13,  2};
     21 
     22 // 验证"基本信息(斐波那契堆的结构)"
     23 void testBasic()
     24 {
     25     int i;
     26     int blen=sizeof(b)/sizeof(b[0]);
     27     FibHeap<int>* hb=new FibHeap<int>();
     28 
     29     // 斐波那契堆hb
     30     cout << "== 斐波那契堆(hb)中依次添加: ";
     31     for(i=0; i<blen; i++)
     32     {
     33         cout << b[i] <<" ";
     34         hb->insert(b[i]);
     35     }
     36     cout << endl;
     37     cout << "== 斐波那契堆(hb)删除最小节点" << endl;
     38     hb->removeMin();
     39     hb->print();
     40 }
     41 
     42 // 验证"插入操作"
     43 void testInsert()
     44 {
     45     int i;
     46     int alen=sizeof(a)/sizeof(a[0]);
     47     FibHeap<int>* ha=new FibHeap<int>();
     48 
     49     cout << "== 斐波那契堆(ha)中依次添加: ";
     50     for(i=0; i<alen; i++)
     51     {
     52         cout << a[i] <<" ";
     53         ha->insert(a[i]);
     54     }
     55     cout << endl;
     56     cout << "== 斐波那契堆(ha)删除最小节点" << endl;
     57     ha->removeMin();
     58     ha->print();
     59 
     60     // 斐波那契堆hb
     61     cout << "== 插入50" << endl;
     62     ha->insert(50);
     63     ha->print();
     64 }
     65 
     66 // 验证"合并操作"
     67 void testUnion()
     68 {
     69     int i;
     70     int alen=sizeof(a)/sizeof(a[0]);
     71     int blen=sizeof(b)/sizeof(b[0]);
     72     FibHeap<int>* ha=new FibHeap<int>();
     73     FibHeap<int>* hb=new FibHeap<int>();
     74 
     75     cout << "== 斐波那契堆(ha)中依次添加: ";
     76     for(i=0; i<alen; i++)
     77     {
     78         cout << a[i] <<" ";
     79         ha->insert(a[i]);
     80     }
     81     cout << endl;
     82     cout << "== 斐波那契堆(ha)删除最小节点" << endl;
     83     ha->removeMin();
     84     ha->print();
     85 
     86     // 斐波那契堆hb
     87     cout << "== 斐波那契堆(hb)中依次添加: ";
     88     for(i=0; i<blen; i++)
     89     {
     90         cout << b[i] <<" ";
     91         hb->insert(b[i]);
     92     }
     93     cout << endl;
     94     cout << "== 斐波那契堆(hb)删除最小节点" << endl;
     95     hb->removeMin();
     96     hb->print();
     97 
     98     // 将"斐波那契堆hb"合并到"斐波那契堆ha"中。
     99     cout << "== 合并ha和hb" << endl;
    100     ha->combine(hb);
    101     ha->print();
    102 }
    103 
    104 // 验证"删除最小节点"
    105 void testRemoveMin()
    106 {
    107     int i;
    108     int alen=sizeof(a)/sizeof(a[0]);
    109     int blen=sizeof(b)/sizeof(b[0]);
    110     FibHeap<int>* ha=new FibHeap<int>();
    111     FibHeap<int>* hb=new FibHeap<int>();
    112 
    113     cout << "== 斐波那契堆(ha)中依次添加: ";
    114     for(i=0; i<alen; i++)
    115     {
    116         cout << a[i] <<" ";
    117         ha->insert(a[i]);
    118     }
    119     cout << endl;
    120     cout << "== 斐波那契堆(ha)删除最小节点" << endl;
    121     ha->removeMin();
    122     //ha->print();
    123 
    124     // 斐波那契堆hb
    125     cout << "== 斐波那契堆(hb)中依次添加: ";
    126     for(i=0; i<blen; i++)
    127     {
    128         cout << b[i] <<" ";
    129         hb->insert(b[i]);
    130     }
    131     cout << endl;
    132     cout << "== 斐波那契堆(hb)删除最小节点" << endl;
    133     hb->removeMin();
    134     //hb->print();
    135 
    136     // 将"斐波那契堆hb"合并到"斐波那契堆ha"中。
    137     cout << "== 合并ha和hb" << endl;
    138     ha->combine(hb);
    139     ha->print();
    140 
    141 
    142     cout << "== 删除最小节点" << endl;
    143     ha->removeMin();
    144     ha->print();
    145 }
    146 
    147 // 验证"减小节点"
    148 void testDecrease()
    149 {
    150     int i;
    151     int blen=sizeof(b)/sizeof(b[0]);
    152     FibHeap<int>* hb=new FibHeap<int>();
    153 
    154     // 斐波那契堆hb
    155     cout << "== 斐波那契堆(hb)中依次添加: ";
    156     for(i=0; i<blen; i++)
    157     {
    158         cout << b[i] <<" ";
    159         hb->insert(b[i]);
    160     }
    161     cout << endl;
    162     cout << "== 斐波那契堆(hb)删除最小节点" << endl;
    163     hb->removeMin();
    164     hb->print();
    165 
    166     cout << "== 将20减小为2" << endl;
    167     hb->update(20, 2);
    168     hb->print();
    169 }
    170 
    171 // 验证"增大节点"
    172 void testIncrease()
    173 {
    174     int i;
    175     int blen=sizeof(b)/sizeof(b[0]);
    176     FibHeap<int>* hb=new FibHeap<int>();
    177 
    178     // 斐波那契堆hb
    179     cout << "== 斐波那契堆(hb)中依次添加: ";
    180     for(i=0; i<blen; i++)
    181     {
    182         cout << b[i] <<" ";
    183         hb->insert(b[i]);
    184     }
    185     cout << endl;
    186     cout << "== 斐波那契堆(hb)删除最小节点" << endl;
    187     hb->removeMin();
    188     hb->print();
    189 
    190     cout << "== 将20增加为60" << endl;
    191     hb->update(20, 60);
    192     hb->print();
    193 }
    194 
    195 // 验证"删除节点"
    196 void testDelete()
    197 {
    198     int i;
    199     int blen=sizeof(b)/sizeof(b[0]);
    200     FibHeap<int>* hb=new FibHeap<int>();
    201 
    202     // 斐波那契堆hb
    203     cout << "== 斐波那契堆(hb)中依次添加: ";
    204     for(i=0; i<blen; i++)
    205     {
    206         cout << b[i] <<" ";
    207         hb->insert(b[i]);
    208     }
    209     cout << endl;
    210     cout << "== 斐波那契堆(hb)删除最小节点" << endl;
    211     hb->removeMin();
    212     hb->print();
    213 
    214     cout << "== 删除节点20" << endl;
    215     hb->remove(20);
    216     hb->print();
    217 }
    218 
    219 int main()
    220 {
    221     // 验证"基本信息(斐波那契堆的结构)"
    222     testBasic();
    223     // 验证"插入操作"
    224     //testInsert();
    225     // 验证"合并操作"
    226     //testUnion();
    227     // 验证"删除最小节点"
    228     //testRemoveMin();
    229     // 验证"减小节点"
    230     //testDecrease();
    231     // 验证"增大节点"
    232     //testIncrease();
    233     // 验证"删除节点"
    234     //testDelete();
    235 
    236     return 0;
    237 }
    View Code

     

    斐波那契堆的C++测试程序

    斐波那契堆的测试程序包括了"插入"、"合并"、"增大"、"减小"、"删除"、"基本信息"等几种功能的测试代码。默认是运行的"基本信息(验证斐波那契堆的结构)"测试代码,你可以根据自己的需要来对相应的功能进行验证!

    下面是基本信息测试代码的运行结果:

    == 斐波那契堆(hb)中依次添加: 18 35 20 42 9 31 23 6 48 11 24 52 13 2 
    == 斐波那契堆(hb)删除最小节点
    == 斐波那契堆的详细信息: ==
     1.    6(3) is root
           9(0) is  6's child
          18(1) is  9's next
          35(0) is 18's child
          20(2) is 18's next
          42(0) is 20's child
          23(1) is 42's next
          31(0) is 23's child
     2.   11(2) is root
          48(0) is 11's child
          24(1) is 48's next
          52(0) is 24's child
     3.   13(0) is root

     

  • 相关阅读:
  • 原文地址:https://www.cnblogs.com/skywang12345/p/3659069.html
  • 最新文章
  • 热门文章
一二三 - 开发者的网上家园