一，介紹
什麼是二項隊列，為什麼會用到二項隊列？
與二叉堆一樣，二項隊列也是優先級隊列的一種實作方式。在 資料結構--堆的實作之深入分析 的末尾 ，簡單地比較了一下二叉堆與二項隊列。
對于二項隊列而言，它可以彌補二叉堆的不足:merge操作的時間複雜度為O(N)。二項隊列的merge操作的最壞時間複雜度為O(logN)。
二項隊列的合并操作為什麼是O(logN)？因為：對于N個結點的二項隊列，最多隻有logN棵二項樹。而合并操作就是合并兩棵高度相同的二項樹。（合并操作是指将二個二項隊列合并，合并這兩個二項隊列中高度相同的二項樹）
二，二項隊列的基本操作及實作
在詳細介紹二項的隊列的基本操作之前，先了解下二項隊列這種資料結構：
1）一個二項隊列是若幹棵樹的集合。也就是說，二項隊列不僅僅是一棵樹，而是多棵樹，并且每一棵樹都遵守堆序的性質，所謂堆序的性質，就是指每個結點都比它的左右子樹中結點要小（小頂堆）。這棵樹稱為“二項樹”
2）二項隊列中的樹高度不同，一個高度至多存在一棵二項樹。将高度為0的二項樹記為 B(0)，高度為 k 的二項樹記為 B(k)
也就是說，對于k>=0，二項隊列中至多存在一棵 B(k)的二項樹。
3）B(k)是由 B(0)、B(1)、B(2)....B(k-1)組成的。B(0)是一棵單節點(2^0 = 1)的樹，B(k)中含有 2^k 個結點。
高度為 k 的二項樹B(k)通過将一棵二項樹B(k-1)附到另一棵二項樹B(k-1)的根上構成。而B(k-1)又可以由B(k-2)附到另一棵B(k-2)的二項樹上，故正如上面提到，B(k)是由 B(0)、B(1)、B(2)....B(k-1)組成的。
4）具有N個結點的二項隊列最多有 logN 棵二項樹。因為，每棵二項樹B(k)中含有2^k個結點。
故：2^0 + 2^1 + 2^2 + .... + 2^k = N，得到 k=logN。k為樹的棵數。
注意到上面提到的是“最多” 有logN 棵二項樹，這說明一個二項隊列可以缺少某棵 B(i) , 0<=i<=k
5）由二項樹中結點個數的性質(B(k)有2^k個結點)，而二項隊列又是若幹二項樹的集合，故二項隊列可以采用二進制數來标記：
如，大小為13(共有13個結點)的二項隊列可以用森林 B(3)、B(2)、B(0)表示，并可以把這種表示寫成 1101，1101以二進制形式表示13，而且還表示了該二項隊列中，不存在B(1)這樣的樹。
介紹了二項隊列的性質或者說邏輯結構，現在介紹下二項隊列的存儲結構。
二項隊列是在内在中如何存儲的呢？（從網上找到一張圖如下：）
首先是需要一個一維數組。該數組中的每個元素存儲一棵二項樹的根結點指針。比如，最右邊的那個數組元素存儲了一顆高度為0的二項樹B(0)。B(0)隻有一個結點，該結點的權值為13。如果數組的長度表示二進制的位數，那麼這個二項隊清單示為 00001101
這說明該二項隊列不存在高度為7、6、5、4、1 這樣的二項樹：B(7)、B(６)、B(５)、B(４)、B(1)
此外，還可以看出：
①數組大小為二項樹的數目乘2加1，或者說二項樹的數目是數組的長度除以2再減去1。二項樹在數組中存儲是按高度排序的。
②數組第 i 号索引處，存儲的是高度為 i 的二項樹。如，第0号索引，存儲高度為0的二項樹，該二項樹隻有一個結點，結點權值為13
除了需要一維數組存儲各棵樹的根結點外，當然還需要儲存各棵二項樹了，二項樹的采用的是連結清單 表示，這裡采用的是“左孩子右兄弟”表示法。
是以，二項隊列的實作類的結構如下：
1 public final class BinomialQueue<AnyType extends Comparable<? super AnyType>>
2 {
3
4 private static final int DEFAULT_TREES = 1;
5
6 private int currentSize; // # items in priority queue
7 private BinNode<AnyType> [ ] theTrees; // An array of tree roots
8
9 /**
10 * Construct the binomial queue.
11 */
12 public BinomialQueue( )
13 {
14 theTrees = new BinNode[ DEFAULT_TREES ];
15 makeEmpty( );
16 }
17
18
19 private static class BinNode<AnyType>
20 {
21 AnyType element; // The data in the node
22 BinNode<AnyType> leftChild; // Left child
23 BinNode<AnyType> nextSibling; // Right child
24 // Constructors
25 BinNode( AnyType theElement )
26 {
27 this( theElement, null, null );
28 }
29
30 //other operations.....
31 }
32 //other operations.....
33 } 第7行是一維數組，第19至23行是采用“左孩子右兄弟”表示法的結點的定義。
①merge操作
merge操作是合并二個二項隊列，合并二項隊列過程中需要合并這兩個二項隊列中 高度相同的二項樹(後面的combineTrees()方法)
假設需要合并二項隊列H(1)和H(2)，合并後的結果為H(3)。合并兩個二項隊列的過程如下：
a)尋找H(1)和H(2)中高度相同的二項樹，調用combineTrees()合并這兩顆二項樹
b)重複 a) 直至樹中不再有高度相同的二項樹為止
代碼分析如下：
1 /**
2 * Return the result of merging equal-sized t1 and t2.
3 */
4 private BinNode<AnyType> combineTrees( BinNode<AnyType> t1, BinNode<AnyType> t2 )
5 {
6 if( t1.element.compareTo( t2.element ) > 0 )
7 return combineTrees( t2, t1 );//第一個參數t1總是代表：根的權值較小的那顆二項樹
8 t2.nextSibling = t1.leftChild;//把權值大的二項樹的左孩子作為權值小的二項樹的右兄弟
9 t1.leftChild = t2;//把權值小的二項樹 作為 權值大的 二項樹 的 左孩子
10 return t1;
11 } combineTrees()方法用來合并兩棵高度相同的二項樹，(注意是二項樹，而不是二項隊列)。樹采用的是左孩子右兄弟表示法。
第4行，t1是根的權值較小的二項樹樹，第8-9行，将根權值較大的那顆二項樹成為根權值較小的二項樹(t1)的子樹，即可完成二項樹的合并。
二項隊列的合并，是二項隊列中高度相同的各個子樹之間的合并。
故merge操作的代碼如下(來自于《資料結構與算法分析Mark Allen Weiss》)：
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 } 重點介紹下二項隊列合并為什麼會有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; 第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)。
代碼如下：
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 } ③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操作。
但是，需要注意的是：二項隊列的實作用到了連結清單，樹中的每個元素存儲在一個結點中，結點之間采用“左孩子右兄弟”表示法進行連結，此外還需要一個額外的數組來儲存各棵二項樹的根結點，存儲開銷要比二叉堆大。
而對于二叉堆的存儲，則簡單得多。它隻需要一個一維數組即可存儲各個元素。
四，參考資料
http://www.cnblogs.com/pacoson/p/5151886.html
《資料結構與算法分析 JAVA語言描述第三版》Mark Allen Weiss著
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)