首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

二项队列分析及实现(2)

二项队列分析及实现(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;
继承事业,薪火相传
很好的帖子,感谢楼主的分享
返回列表