电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 二项队列分析及实现(2) [打印本页]

作者: yuyang911220 时间: 2016-8-20 20:28 标题: 二项队列分析及实现(2)

。

二项队列的合并，是二项队列中高度相同的各个子树之间的合并。
故merge操作的代码如下(来自于《数据结构与算法分析Mark Allen Weiss》)：
[url=]

[/url]
1 /** 2 * Merge rhs into the priority queue. 合并this 和 rhs 这两个二项队列 3 * rhs becomes empty. rhs must be different from this. 4 * @param rhs the other binomial queue. 5 */ 6 public void merge( BinomialQueue<AnyType> rhs ) 7 { 8 if( this == rhs ) // Avoid aliasing problems.不支持两个相同的二项队列合并 9 return;10 11 currentSize += rhs.currentSize;//新合并后的二项队列中的结点个数12 13 if( currentSize > capacity( ) )14 {15 int newNumTrees = Math.max( theTrees.length, rhs.theTrees.length ) + 1;16 expandTheTrees( newNumTrees );17 }18 19 BinNode<AnyType> carry = null;20 for( int i = 0, j = 1; j <= currentSize; i++, j *= 2 )21 {22 BinNode<AnyType> t1 = theTrees[ i ];23 BinNode<AnyType> t2 = i < rhs.theTrees.length ? rhs.theTrees[ i ] : null;24 //合并分8种情况25 int whichCase = t1 == null ? 0 : 1;26 whichCase += t2 == null ? 0 : 2;27 whichCase += carry == null ? 0 : 4;28 29 switch( whichCase )30 {31 case 0: /* No trees */32 case 1: /* Only this */33 break;34 case 2: /* Only rhs */35 theTrees[ i ] = t2;36 rhs.theTrees[ i ] = null;37 break;38 case 4: /* Only carry */39 theTrees[ i ] = carry;40 carry = null;41 break;42 case 3: /* this and rhs */43 carry = combineTrees( t1, t2 );44 theTrees[ i ] = rhs.theTrees[ i ] = null;45 break;46 case 5: /* this and carry */47 carry = combineTrees( t1, carry );48 theTrees[ i ] = null;49 break;50 case 6: /* rhs and carry */51 carry = combineTrees( t2, carry );52 rhs.theTrees[ i ] = null;53 break;54 case 7: /* All three */55 theTrees[ i ] = carry;56 carry = combineTrees( t1, t2 );57 rhs.theTrees[ i ] = null;58 break;59 }60 }61 62 for( int k = 0; k < rhs.theTrees.length; k++ )63 rhs.theTrees[ k ] = null;//合并完成之后,释放rhs内存64 rhs.currentSize = 0;65 } [url=]

[/url]

重点介绍下二项队列合并为什么会有8种情况：
第25至27行，这8种情况可以用三个二进制位来表示：
         //合并分8种情况          int whichCase = t1 == null ? 0 : 1;          whichCase += t2 == null ? 0 : 2;          whichCase += carry == null ? 0 : 4;
0<=whichCase<=7，一共8种情况。只分析一种情况，其他情况类似分析：
分析有rhs和this的情况。即，需要将 this 和 rhs 这两棵二项树合并，this代表当前二项树。二进制表示为 011
t1(this)不为空，whichCase=1，然后 t2为rhs，也不为空，故whichCase再加2。这里加2的原因是rhs是二进制中的第2位。

situation          carry rhs this
no trees          0       0    0
only this          0       0    1
only rhs          0       1    0
only  carry       1       0    0
this and rhs       0       1    1
.....
.....
All                      1       1    1
carry表示上一步合并二项树过程上，生成的一棵新二项树。

确定了哪种合并情况后，再来看看对这些情况是如何处理的：
            case 0: /* No trees */             case 1: /* Only this */             break;

作者: yuchengze 时间: 2016-8-21 14:52

很好的帖子，感谢楼主的分享

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)