斐波那契堆

表示

由一组最小堆有序树构成,n[H]记录此堆节点的数量

    struct FibHeapNode
        key_t k ;
        int degree ;
        FibHeapNode *parent ;
        FibHeapNode *child ;
        FibHeapNode *left, *right ;    //兄弟之间组成循环链表
        bool mark ;                    //布尔值,指示上一次成为一个节点的子女以来,是否失掉一个孩子(True/False)
        min[H]
          |
          4 ---------------------- 17 ---------------------- 24     #根表
       /  |  \                     |
     18t  32  38                   30                    #带t mark=true
      |        |
     39t      41

循环链表的好处: 1.可以在O(1)时间内删除一个节点 2.可以在O(1)时间内合并两条链表

为什么二项堆不使用循环链表: 1.二项堆的根表的degree严格递增==>合并链表不能体现循环链表的好处 2.单向链表可以在O(1)的时间内删除sibling节点

操作

插入一个节点

    FibHeapInsert( H, x )       // T(n) = O(1)
        parent[x] = nil ;
        child[x] = nil ;
        left[x] = nil ;
        right[x] = nil ;
        mark[x] = False ;
        degree[x] = 0 ;

        insert x into root list in the left side of min[H] ;

        if min[H] == nil
            min[H] = x ;
        else
            key[min[H]] > key[x] && min[H] = x ;
        n[H]++ ;

寻找最小节点

    FibHeapMin( H )     // T(n) = O(1)
        return min[H] ;

创建一个新的斐波那契堆

    MakeFibHeap( )          // T(n) = O(1)
        H = Allocate( ) ;
        min[H] = nil ;
        n[H] = 0 ;
        return H ;

合并两个斐波那契堆

    FibHeapUnion( H1, H2 )  // T(n) = O(1)
        H = MakeFibHeap( ) 
        min[H] = min[H1] ;
        
        connect root list H2 with root list H ;
        n[H] = n[H1] + n[H2] ;
        key[min[H1]] > key[min[H2]] && min[H] = min[H2] ;

        free( H1 ) ;
        free( H2 ) ;
        return H ;

抽取最小节点

    FibHeapExtractMin( H )  //T(n) = O( D(n) ) : 根表节点的最大度数
        z = min[H] ;
        for each child x of z 
            insert x into root list H ;
            parent[x] = nil ;
        
        remove z from root list H, and DO NOT destroy any pointer of z;

        if right[z] == z    //z是根表中唯一的元素
            min[H] = nil ; 
        else
            min[H] = right[z] ;

        Consolidata( H ) ;
        n[H]-- ;
        return z ;

    /*-------------------------------*/
    Consolidata( H )
    /*
        此过程反复执行以下操作,直到根表节点都有一个不同的degree值
        1.找出具有相同degree值的x和y,且 key[x] <= key[y]
        2.使y成为x的子女,将y从根表中删除由FibHeapLink完成
    */
        for i = 0 to D( n(H) )      //D(n(H))是根表节点的最大度数
            A[i] = nil ;            //数组A用来临时保存根表中的节点

        for each w in root list H
            x = w ;
            d = degree[x] ;

            while A[d] != nil
            /*
                FibHeapLink完成后,degree[x]加1,这样可以继续合并A[d]与x具有相同degree的根
            */
                y = A[d] ;
                if key[y] > key[x]
                    exchange( x, y ) ; //交换关键字和卫星数据
                FibHeapLink( H, y, x ) ;
                A[d] = nil ;
                d++ ;
            /*
                while循环举例:
                A数组           A数组            A数组          
                1-2-3-\  ===>   \-2-3-\   ===>   \-\-3-\   ===>
                degree[x]=1     degree[x]=2      degree[x]=3  
                d = 1           d = 2            d = 3

                A数组
                \-\-\-\   ===>   \-\-\-x
                degree[x]=4      循环结束
                d = 4
                
                循环不变式: d = degree[x]
                初始化: 第一次进入循环时,不变式成立
                保持: x和y链接,degree[x]+1,循环结束时d也加1,
                      所以恢复 d = degree[x]
                结束: d = degree[x]
            */

            A[d] = x ;


        min[H] = the node with minimal key of root list H ;

    /*--------------------------------*/
    FibHeapLink( H, y, x )
        remove y from root list H ;
        make y a child of x ;
        degree[x]++ ;
        mark[y] = False ;

减小一个关键字的值

    FibHeapDecreaseKey( H, x, k )   //T(n) = O(1),平摊代价
        if k >= key[x]
            return ERROR ;
        key[x] = k ;
        y = parent[x] ;

        if y != nil && key[x] < key[y] 
            Cut( H, x, y ) ;        //将x从y的子女中分离,并将x插入H的根表中
            CascadingCut( H, y ) ;

        if key[x] < key[min[H]]
            min[H] = x ;

    /*---------------------------------*/
    Cut( H, x, y )
        remove x from child list of y ;
        degree[y]-- ;
        add x into root list H ;
        parent[x] = nil ;
        mark[x] = False ;

    /*---------------------------------*/
    CascadingCut( H, y )
        z = parent[y] ;
        if z != nil 
            if mark[y] == False ;
                mark[y] = True ;
            else                            //当mark为True时,说明其已经失去了
                Cut( H, y, z ) ;            //一个子女,现在已经失去了第二个子
                CascadingCut( H, z ) ;      //女,所以切断其与父节点z的联系,
                                            //成为一个新根节点

删除一个关键字

    FibHeapDelete( H, x )   //T(n) = O( D(n) )
        FibHeapDecreaseKey( H, x, MIN_VALUE ) ;
        FibHeapExtractMin( H ) ;