二项队列
更多内容参考这篇文章
数据结构–二项队列分析及实现
众所周知，只需要一个数组，我们就能实现二叉堆。二叉堆的Insert，DeleteMin均能以 O(logN) 执行，BuildHeap 和 Merge 能够以 O(logN) 执行。
为了降低 Merge 复杂度，人们不得不使用指针，这就诞生了左式堆。左式堆本质上是一个二叉树，斜堆是左式堆的一个变体，各方面性能和左式堆相似。
左式堆(leftist heap)和斜堆(skew heap)实现了 O(logN) 的Merge，并且基于Merge实现了 Insert 和 DeleteMin 操作。
这么一来虽然 Merge 的性能被搞上去了，但是 Insert 的性能却下来了。毕竟，从平均的角度看，左式堆和斜堆Insert的平均复杂度是O(logN) ，而二叉堆Insert的平均复杂度是O(log1)。
因此有人发明了二项队列(binomial queue)，该数据结构Insert，DeleteMin和Merge的最坏复杂度为O(logN) ，而且Insert的平均复杂度是O(log1) 。
什么是二项队列？
不是数组。也不是树。二项队列的真身是一个小数组+若干棵树。
设数组为root[]，每棵树为Bk，k为这棵树的高度。
数组root[]里装的是每棵树的根节点指针，root[i] 里面的元素要么是空指针，要么是一个固定大小的树的根节点指针，这棵树的高度为 i，大小为 2i 。如图1所示。
深度 d 处的节点数是二项系数 Ckd
每棵树自身都要满足堆的性质，即所有子节点的值都比父节点的值大。
展示 H1和 H2两个二项队列的实例，如图 2和图 3。
二项队列怎么Merge？
举个例子，我们将上文提到的 H1 和 H2 合并，得到 H3 。合并后，新二项队列的 B0 来自 H1 ，B1 来自 H2 。
B2 有两个，所以我们将 H1 和 H2 的 B2 合并。让大根(12)成为小根(11)的子树，并且将小根作为 H3 的B3 。因此 H3 中没有高度为 2 的树
得到的H3是一个新的二项队列，元素个数为11(=1+2+8)，如图4所示。
可见，二项队列的合并有点像二进制数加法：(110)2 + (101)2 = (1011)2，某一位满了就进位。
二项队列怎么Insert？
想要将一个元素 e 插入到二项队列 H 中，直接将 e 视为一个仅包含1个元素的二项队列 He ，然后合并 H 和 He
Insert的最坏情形运行时间 O(logN) 。
二项队列怎么DeleteMin？
因为每一个树都具有堆的性质，所以二项队列的最小值一定在某一个树的根上。遍历所有树的根，找到这个最小值，需要 O(logN) 的时间。假定最小值所在的树为 Bk ，删掉这个根节点，一定会剩下k个子树，高度分别为k-1，k-2，…，1，0。
将原二项队列去掉 Bk ，再与Bk 的 k 个子树合并，如图 5 和图 6，需要 O(logN) 的时间。
DeleteMin最坏情形运行时间 O(logN)
二项队列实现
二项树合并图解：
二项队列的操作主要有：
- 合并：Merge
- 删除最小值：DeleteMin
- 插入节点：InsertElement
- 清空二项队列：MakeEmpty
- 查找最小元素：FindMin
根据以上分析，有如下数据结构定义：
public final class BinomialQueue<AnyType extends Comparable<? super AnyType>>
{
private static final int DEFAULT_TREES = 1;
private int currentSize; // # items in priority queue
private BinNode<AnyType> [ ] theTrees; // An array of tree roots
/**
* Construct the binomial queue.
*/
public BinomialQueue( )
{
theTrees = new BinNode[ DEFAULT_TREES ];
makeEmpty( );
}
private static class BinNode<AnyType>
{
AnyType element; // The data in the node
BinNode<AnyType> leftChild; // Left child
BinNode<AnyType> nextSibling; // Right child
// Constructors
BinNode( AnyType theElement )
{
this( theElement, null, null );
}
BinNode( AnyType theElement, Node<AnyType> lt, Node<AnyType> nt )
{ element = theElement; leftChild = lt; nextSibling = nt;}
//数组大小为二项树的数目 * 2 - 1
//例如，二项树数目为2，则 1 << 2 - 1 = 3 001 << 2 = 100
private int capacity()
{
return ( 1 << theTrees.length ) - 1;
}
//other operations.....
}
合并核心函数(合并高度相等的树)
/**
* Return the result of merging equal-sized t1 and t2.
*/
private BinNode<AnyType> combineTrees( BinNode<AnyType> t1, BinNode<AnyType> t2 )
{
if( t1.element.compareTo( t2.element ) > 0 )
return combineTrees( t2, t1 );
t2.nextSibling = t1.leftChild;
t1.leftChild = t2;
return t1;
}
combineTrees()方法用来合并两棵高度相同的二项树，(注意是二项树，而不是二项队列)。树采用的是左孩子右兄弟表示法。
merge操作的代码如下(来自于《数据结构与算法分析Java 语言描述》)
/**
* Merge rhs into the priority queue. 合并this 和 rhs 这两个二项队列
* rhs becomes empty. rhs must be different from this.
* @param rhs the other binomial queue.
*/
public void merge( BinomialQueue<AnyType> rhs )
{
if( this == rhs ) // Avoid aliasing problems.不支持两个相同的二项队列合并
return;
currentSize += rhs.currentSize;//新合并后的二项队列中的结点个数
if( currentSize > capacity( ) )
{
int newNumTrees = Math.max( theTrees.length, rhs.theTrees.length ) + 1;
expandTheTrees( newNumTrees );
}
BinNode<AnyType> carry = null;
for( int i = 0, j = 1; j <= currentSize; i++, j *= 2 )
{
BinNode<AnyType> t1 = theTrees[ i ];
BinNode<AnyType> t2 = i < rhs.theTrees.length ? rhs.theTrees[ i ] : null;
//合并分8种情况，0 <= whichcase <= 7, 000--111
int whichCase = t1 == null ? 0 : 1;
whichCase += t2 == null ? 0 : 2;
whichCase += carry == null ? 0 : 4;
switch( whichCase )
{
case 0: /* No trees */
case 1: /* Only this */
break;
case 2: /* Only rhs */
theTrees[ i ] = t2;
rhs.theTrees[ i ] = null;
break;
case 4: /* Only carry */
theTrees[ i ] = carry;
carry = null;
break;
case 3: /* this and rhs */
carry = combineTrees( t1, t2 );
theTrees[ i ] = rhs.theTrees[ i ] = null;
break;
case 5: /* this and carry */
carry = combineTrees( t1, carry );
theTrees[ i ] = null;
break;
case 6: /* rhs and carry */
carry = combineTrees( t2, carry );
rhs.theTrees[ i ] = null;
break;
case 7: /* All three */
theTrees[ i ] = carry;
carry = combineTrees( t1, t2 );
rhs.theTrees[ i ] = null;
break;
}
}
for( int k = 0; k < rhs.theTrees.length; k++ )
rhs.theTrees[ k ] = null;//合并完成之后,释放rhs内存
rhs.currentSize = 0;
}
carry表示上一步合并二项树过程上，生成的一棵新二项树。
| 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 |
来分析下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，用carry表示。这也是上面提到的” 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
注：当有三棵高度相同的二项树时，其中一棵是上一步合并生成的carry，另外两棵是原来二项队列中存在的。并不是把其中两棵根权值较小的二项树进行合并，而是合并原来二项队列中存在的那两棵：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 的二项树有关，平均情况下的时间复杂度为O(1)。
代码如下：
/**
* Insert into the priority queue, maintaining heap order.
* This implementation is not optimized for O(1) performance.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
merge( new BinomialQueue<>( x ) );
}
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’’
// 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;
}
3）原来的二项队列，删除B(i)这棵根的权值最小的二项树后，得到的新的二项队列 H’
// Construct H'
theTrees[ minIndex ] = null;
currentSize -= deletedQueue.currentSize + 1;
4）合并 H’’ 和 H’ 即可
merge( deletedQueue );
整个deleteMin的实现代码如下：
/**
* 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;
}
二项队列与二叉堆的比较
| 基本操作 | insert(平均情况下) | deleteMin | merge |
|---|---|---|---|
| 二项队列: | O(1) | O(logN) | O(logN) |
| 二叉堆： | O(1) | O(logN) | O(N) |
可见，二项队列有效地支持了merge操作。
但是，需要注意的是：二项队列的实现用到了链表，树中的每个元素存储在一个结点中，结点之间采用“左孩子右兄弟”表示法进行链接，此外还需要一个额外的数组来保存各棵二项树的根结点，存储开销要比二叉堆大。
而对于二叉堆的存储，则简单得多。它只需要一个一维数组即可存储各个元素。