跳转至

5 Binomial Queue

文本统计：约 628 个字 • 100 行代码

5.1 Definition

Structure: A binomial queue is not a heap-ordered tree, but rather a collection of heap-ordered trees, known as a forest. Each heap-ordered tree is a binomial tree.

How to construct?

A binomial tree of height 0 is a one-node tree.

A binomial tree, \(B_k\), of height \(k\) is formed by attaching a binomial tree, \(B_{k – 1}\), to the root of another binomial tree, \(B_{k – 1}\).

Observation :

\(B_k\) consists of a root with \(k\) children, which are \(B_0,B_1,B_2\dots,B_k\). \(B_k\) has exactly \(2^k\) nodes. The number of nodes at depth \(d\) is \(C_k^d\).

一个数组可以唯一地被一个二项堆来表示，A priority queue of any size can be uniquely represented by a collection of binomial trees. 比如说13就可以表示为\(2^0+0\times2^1+2^2+2^3=1101_2\)

5.2 Operations

Findmin

最小值一定在根处取到，一共有\(\lceil \log N \rceil\)个根，所以\(T_p=(\log N)\)

Merge

Must keep the trees in the binomial queue sorted by height.

Insert

把它看作是合并的特殊情况。

时间复杂度分析：插入一次的时间复杂度可能是\(O(\log N)\)也可能是\(O(1)\)，那么我们要通过均摊分析来计算均摊复杂度。设置势能函数为#trees, 第i次最小的未出现的堆为\(B_j\)，那么

\[ \hat c_i=c_i+\Phi_i-\Phi_{i-1}=1+j+1-j=2 \]

则

\[ \sum_{i=1}^n\hat c_i=\sum_{i=1}^nc_i+\Phi_n-\Phi_0=O(n) \]

而 \(\Phi_n>0,\Phi_0=0\)，那么相应的均摊复杂度就为\(O(1)\)了

DeleteMin(H)

5.3 Implementation

Binomial queue = array of binomial trees

Operation Property Solution
Delete Min Find all the subtrees quickly 需要快速获得所有子树 Left-child-next-sibling with linked lists 按照孩子相连的方法构建链表
Merge The children are ordered by their sizes 孩子需要按照顺序排放 The new trees will be the largest. Hence maintain the subtrees in decreasing sizes 根节点指向最大的子孩子，方便合并。

为什么子孩子的顺序是从大到小连接？因为合并的时候是将两棵一样大的数连接在一起，其中一棵树变成另一棵树的子树，肯定是最大的孩子，那么改指针的时候就只需要先将合并的树的nextsibling指向原先最大的孩子，再将根的Leftchild指向新孩子即可。如果反向的话就会造成还需要从头遍历一遍。

相应的数据结构

typedef struct BinNode *Position;
typedef struct Collection *BinQueue;
typedef struct BinNode *BinTree;  /* missing from p.176 */

struct BinNode 
{ 
    ElementType     Element;
    Position        LeftChild;  //最大的孩子
    Position        NextSibling;    //兄弟节点
} ;

struct Collection 
{ 
    int         CurrentSize;  /* total number of nodes */
    BinTree TheTrees[ MaxTrees ];
} ;

合并树的操作，将根元素小的放上面

BinTree
CombineTrees( BinTree T1, BinTree T2 )
{  /* merge equal-sized T1 and T2 */
    if ( T1->Element > T2->Element )
        /* attach the larger one to the smaller one */
        return CombineTrees( T2, T1 );
    /* insert T2 to the front of the children list of T1 */
    T2->NextSibling = T1->LeftChild;
    T1->LeftChild = T2;
    return T1;
}

合并两个二项堆的操作

BinQueue  Merge( BinQueue H1, BinQueue H2 )
{   
    BinTree T1, T2, Carry = NULL;   
    int i, j;
    //合并后的节点数超过容量
    if ( H1->CurrentSize + H2-> CurrentSize > Capacity )  ErrorMessage();
    //将H2合并到H1中去，改变H1的大小
    H1->CurrentSize += H2-> CurrentSize;
    //从B0开始合并，注意进位
    for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
        T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i]; /*current trees */
        switch( 4*!!Carry + 2*!!T2 + !!T1 ) { 
        //000代表两棵树都没有且无进位
        case 0: /* 000 */
        //001代表只有H1有这棵树，H2没有且无进位，什么也不用操作
        case 1: /* 001 */  break;   
        //010代表只有H2有这棵树，H1没有且无进位，那么将H2的部分给H1
        case 2: /* 010 */  H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
        //100代表只有进位，那么只需将进位上来的那一棵树给到H1即可，并清空进位
        case 4: /* 100 */  H1->TheTrees[i] = Carry; Carry = NULL; break;
        //011代表H1和H2均有这个大小的树，那么只需要将两者合并并交给进位即可
        case 3: /* 011 */  Carry = CombineTrees( T1, T2 );
                        H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
        //其余的类似
        case 5: /* 101 */  Carry = CombineTrees( T1, Carry );
                        H1->TheTrees[i] = NULL; break;
        case 6: /* 110 */  Carry = CombineTrees( T2, Carry );
                        H2->TheTrees[i] = NULL; break;
        case 7: /* 111 */  H1->TheTrees[i] = Carry; 
                        Carry = CombineTrees( T1, T2 ); 
                        H2->TheTrees[i] = NULL; break;
        } /* end switch */
    } /* end for-loop */
    return H1;
}

删除最小节点的操作DeleteMin

ElementType  DeleteMin( BinQueue H )
{   
    //DeletedQueue用来存储删除最小值的孩子序列的
    BinQueue DeletedQueue; 
    Position DeletedTree, OldRoot;
    ElementType MinItem = Infinity;  /* the minimum item to be returned */  
    int i, j, MinTree; /* MinTree is the index of the tree with the minimum item */

    if ( IsEmpty( H ) )  {  PrintErrorMessage();  return –Infinity; }

    for ( i = 0; i < MaxTrees; i++) 
    {  /* Step 1: find the minimum item */
        if( H->TheTrees[i] && H->TheTrees[i]->Element < MinItem ) { 
        MinItem = H->TheTrees[i]->Element;  
        MinTree = i;    } 
    } 

    DeletedTree = H->TheTrees[ MinTree ];  
    H->TheTrees[ MinTree ] = NULL;   /* Step 2: remove the MinTree from H => H’ */ 
    OldRoot = DeletedTree;   /* Step 3.1: remove the root */ 
    //把最大的孩子取出来
    DeletedTree = DeletedTree->LeftChild;   
    free(OldRoot);
    DeletedQueue = Initialize();   /* Step 3.2: create H” */ 
    DeletedQueue->CurrentSize = ( 1<<MinTree ) – 1;  /* 2^MinTree – 1 */
    //构建DeletedQueue
    for ( j = MinTree – 1; j >= 0; j – – ) {  
        //同辈之间不在以指针链接，
        DeletedQueue->TheTrees[j] = DeletedTree;
        DeletedTree = DeletedTree->NextSibling;
        DeletedQueue->TheTrees[j]->NextSibling = NULL;
    } 

    H->CurrentSize  – = DeletedQueue->CurrentSize + 1;
    H = Merge( H, DeletedQueue ); /* Step 4: merge H’ and H” */ 
    return MinItem;
}

5.4 斐波那契堆

优化了decreasekey的均摊时间

相关文章：斐波那契堆(Fibonacci heap)原理详解(附java代码实现) - 转瞬之夏 - 博客园 (cnblogs.com)

总结

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！