。
二项队列的合并，是二项队列中高度相同的各个子树之间的合并。
故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; |
