二项堆

二项树Bk

组成

  1. 一个节点 ; k = 0
  2. 两棵Bk-1树连接而成,其中一棵Bk-1树是另一棵Bk-1树最左边的孩子 ; k > 0

性质

  1. 共有2的k次方个节点
  2. 树的高度为k
  3. 在深度为i处恰有 k! / i! (k-i)! (即:k的i组合)
  4. 在Bk二项树中,根节点的子女从右到左分别是B0~~Bk-1二项树的根节点

二项堆H

由二项树组成

性质

  1. 节点的关键字大于或等于其父节点的关键字
  2. 对任意非负整数k,在H中至多只有一颗Bk数
  3. H中至多包含 logn + 1 棵二项树 (n为节点数)

n的二进制表示中有 logn + 1 位,如< blogn, blogn-1, … , b0 > 二项树Bi出现于H中,当且仅当bi = 1 ; 例:包含13个节点的二项堆H, 13 = 1101B, H就包含B3,B2,B0

表示

    struct BinomialHeapNode                 // 各二项树的根组成的链表:二根表 
        struct BinomialHeapNode *parent ;   
        struct BinomialHeapNode *child ;    // 左孩子
        struct BinomialHeapNode *sibling ;  // 右兄弟
        int degree ;                        // 各根的度数严格递增
        key_t key ;

二项堆的操作

创建一棵新二项堆
    MakeBinomialHeap( )         // T(n) = O(1)
        head[H] = nil ;
寻找最小关键字
    BinomialHeapMin( H )        // 最大检查 logn + 1 个节点, T(n) = O(lgn)
        x = nil ;                   // 用来返回最小值的节点指针
        y = Head[H] ;
        min = MAX_VALUE ;
        
        while y != nil ;
            if key[y] < min 
                min = key[y] ;
                x = y ;
        
            y = sibling[y] ;

        return x ;
合并两个二项堆
合并两棵二项树
    BinomialLink( x, y )            // T(n) = O(1)
        parent[x] = y ;                  // 将以节点x为根的Bk-1数和以y为根的Bk-1树
        sibling[x] = child[y] ;     // 合并成Bk树,且以y为根节点
        child[y] = x ;
        degree[y]++ ;
合并两个二项堆

注意事项:

  1. 避免出项degree为1-1-1-2的二项树(当然连续出项3个degree为”1”的二项树是不可能的),但有可能出现2-2-2-4这种排列的二项树,合并后避免出现4-2-4,而只能出现2-4-4
  2. 当调用BinomialLink函数时,是将两棵树合并成一个数,所以要特别注意当前正在处理的二项树的根节点的取值
    BinomialHeapUnion( H1, H2 )     // T(n) = O(lgn)
        H = MakeBinomialHeap( ) ;
        head[H] = BinomialHeapMerge( H1, H2 ) ;  //以degree为关键字,将两条二根表合并成一条二根表

        if head[H] == nil 
            return ;

        prev_x = nil ;
        x = head[H] ;
        next_x = sibling[x] ;     //因为 head[H] == nil 就返回了,所以 x!=nil

        while next_x != nil
            if degree[x] != degree[next_x] || \
               ( sibling[next_x] != nil && \
                degree[next_x] == degree[sibling[next_]] )
                prev_x = x ;
                x = next_x ;      //避免注意事项1出现
            //以下情况需要合并两棵二项树
            else if key[x] <= key[next_x]       // 处理注意事项2
                sibling[x] = sibling[next_x] ; 
                BinomialLink( next_x, x ) ;
            else
                if prev_x == nil ;
                    head[H] = next_x ;
                else
                    prev_x = next_x ;
                BinomialLink( x, next_x ) ;
                x = next_x ;            // 变更当前所操作的x节点
                                        //因为next_x保留在二根表中
            next_x = sibling[x] ;
插入一个节点
    BinomialHeapInsert( H, x )      // T(n) = O(lgn)
        H1 = MakeBinomialHeap( ) ;
        head(H1) = x ;
        
        parent[x] = nil ;
        child[x] = nil ;
        sibling[x] = nil ;
        degree[x] = 0 ;

        H = BinomialHeapUnion( H, H1 ) ;
抽取最小关键字节点
    BinomialHeapExtractMin( H )       // T(n) = O(lgn)
        find the binomial tree B with minimal key in binomial heap H ;
        remove B from H ;

        H1 = MakeBinomialHeap( ) ;
        make head[H1] = child tree of B reversed by degree ;

        H = BinomialHeapUnion( H, H1 ) ;

        return x ;
减小关键字的值
    BinomialHeapDecreaseKey( H, x, k )      // T(n) = O(lgn)
        if key[x] < k 
            return ERROR ;

        key[x] = k ;
        while parent[x] != nil && key[x] < key[parent[x]]
            swap( x, parent[x] ) with key and datas ;
            x = parent[x] ;
删除关键字
    BinomialHeapDelete( H, x )
        BinomialHeapDecreaseKey( H, x, MIN_VALUE ) ;
        BinomialHeapExtractMin( H ) ;