二项队列分析及实现(3) color, null, 黄色

yuyang911220

第0种情况，表示没有树需要合并。第1种情况表示，只有this (当前二项树)树。什么叫只有当前二项树呢？（引用网友的一张图：）

黄色节点表示的是二项队列H(1)，绿色节点表示的二项队列H(2)，红色节点表示合并二项队列H(1)和H(2)之后，生成的新的二项队列H(3)。
H(2)中有一棵节点权值为13的高度为1的二项树，而H(1)中没有高度为1的二项树。此时就是rhs == null。即只有当前二项树(this树)

再来分析下case3情况：
              case 3: /* this and rhs */                carry = combineTrees( t1, t2 );                theTrees[ i ] = rhs.theTrees[ i ] = null;                break;
如上图，H(1)中有一棵根为12高度为1的二项树；H(2)中也有一棵高度为1，但根为14的二项树。此时this 和 rhs 都不为null。
调用combineTress(t1,t2)方法合并成一棵新的二项树，该二项树高度为2，用carray表示。这也是上面提到的” carry表示上一步合并二项树过程上，生成的一棵新二项树。“
生成carry之后，H(1)和H(2)中都已经没有高度为1的二项树了，因此执行： theTrees[ i ] = rhs.theTrees[ i ] = null;

再来分析下case7情况：

              case 7: /* All three */                theTrees[ i ] = carry;                carry = combineTrees( t1, t2 );                rhs.theTrees[ i ] = null;                break;

还是参考上面图：H(1)、H(2)在执行了case3之后，这二个二项队列一共有三棵高度为2的二项树了。
第一棵是：case3中生成的。它的根结点的权值为14
第二棵是：H(1)中原来存在的。它的根结点的权值为12

第三棵是：H(2)中原来存在的。它的根结点的权值为23
因此，whichCase的值为7=1+2+4
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
代码中对该情况的处理是这样的(代码处理与图中画的有点不一样：图中画的是将两棵根的权值较小的二项树(第一棵和第二棵)合并  而代码中合并的是第二棵和第三棵。
也就是说，当有三棵高度相同的二项树时，其中一棵是上一步合并生成的carray，另外两棵是原来二项队列中存在的。并不是把其中两棵根权值较小的二项树进行合并，而是合并原来二项队列中存在的那两棵：carry = combineTrees( t1, t2 );总之，在进行合并时，合并的规则并不是：选择两棵根的权值较小的二项树合并。而是根据代码中的case情况来进行合并。
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
数组位置 i 处 保存上一步生成的高度为2的二项树。 theTrees[ i ] = carry;
合并原来存在的那两棵高度为2的二项树， carry = combineTrees( t1, t2 );
合并之后，释放rhs占用的空间， rhs.theTrees[ i ] = null;
至此，合并操作分析完毕，其他情况的合并类似于上面的分析。

②insert 操作
insert操作可以看作是特殊的合并操作。即rhs二项队列中只有一棵高度为0的二项树。插入操作的复杂度与是否存在高度为 i 的二项树有关，具体分析参考Mark Allen Weiss的书籍。平均情况下的时间复杂度为O(1)。
代码如下：
[url=][/url]
1     /**2      * Insert into the priority queue, maintaining heap order.3      * This implementation is not optimized for O(1) performance.4      * @param x the item to insert.5      */6     public void insert( AnyType x )7     {8         merge( new BinomialQueue<>( x ) );9     }[url=][/url]


③deleteMin操作
deleteMin操作的步骤如下：
1）寻找一棵具有最小权值的根的二项树，设为B(i)。
        int minIndex = findMinIndex( );
        AnyType minItem = theTrees[ minIndex ].element;

        BinNode<AnyType> deletedTree = theTrees[ minIndex ].leftChild;

2）删除B(i)的根，得到若干棵二项树:B(0)、B(1)...B(i-1)。这些二项树组成一个新的二项队列 H''
[url=][/url]
        // Construct H''        BinomialQueue<AnyType> deletedQueue = new BinomialQueue<>( );        deletedQueue.expandTheTrees( minIndex + 1 );                deletedQueue.currentSize = ( 1 << minIndex ) - 1;        for( int j = minIndex - 1; j >= 0; j-- )        {            deletedQueue.theTrees[ j ] = deletedTree;            deletedTree = deletedTree.nextSibling;            deletedQueue.theTrees[ j ].nextSibling = null;        }[url=][/url]


3）原来的二项队列，删除B(i)这棵根的权值最小的二项树后，得到的新的二项队列 H'
        // Construct H'        theTrees[ minIndex ] = null;        currentSize -= deletedQueue.currentSize + 1;

4）合并 H'' 和 H' 即可
        merge( deletedQueue );

整个deleteMin的实现代码如下：
[url=][/url]
    /**     * Remove the smallest item from the priority queue.     * @return the smallest item, or throw UnderflowException if empty.     */    public AnyType deleteMin( )    {        if( isEmpty( ) )            throw new UnderflowException( );        int minIndex = findMinIndex( );        AnyType minItem = theTrees[ minIndex ].element;        BinNode<AnyType> deletedTree = theTrees[ minIndex ].leftChild;        // Construct H''        BinomialQueue<AnyType> deletedQueue = new BinomialQueue<>( );        deletedQueue.expandTheTrees( minIndex + 1 );                deletedQueue.currentSize = ( 1 << minIndex ) - 1;        for( int j = minIndex - 1; j >= 0; j-- )        {            deletedQueue.theTrees[ j ] = deletedTree;            deletedTree = deletedTree.nextSibling;            deletedQueue.theTrees[ j ].nextSibling = null;        }        // Construct H'        theTrees[ minIndex ] = null;        currentSize -= deletedQueue.currentSize + 1;        merge( deletedQueue );                return minItem;    }[url=][/url]


三，二项队列与二叉堆的比较
基本操作：     insert(平均情况下)          deleteMin          merge
二项队列：      O(1)                            O(logN)             O(logN)
二叉堆：         O(1)                            O(logN)             O(N)
可见，二项队列有效地支持了merge操作。
但是，需要注意的是：二项队列的实现用到了链表，树中的每个元素存储在一个结点中，结点之间采用“左孩子右兄弟”表示法进行链接，此外还需要一个额外的数组来保存各棵二项树的根结点，存储开销要比二叉堆大。
而对于二叉堆的存储，则简单得多。它只需要一个一维数组即可存储各个元素。

yuchengze

很不错的帖子，路过帮顶