本文在上述的基礎上介紹優先佇列的另外一種支持高效合并操作的實作——二項佇列，原來在介紹二叉堆和左式堆的時候喜歡從結構性和堆序性兩個方面介紹，它們二者都是特殊的二叉樹結構，但是二項佇列不能單純的從結構性和堆序性兩個方面介紹了因為二項佇列并不是我們熟悉的樹結構，而是樹的集合——森林,本篇文章從二項佇列的結構性出發介紹二項佇列的基本原理，
一丶二項佇列的結構性
二項佇列是一群樹的集合，是森林，是特殊的森林，這個森林的特殊之處在于組成森林的樹都是二項樹，下圖就是最為典型的二項佇列，
圖1 典型的二項佇列
圖1所示的是一個典型的二項佇列，它是由四課樹組成的森林，接下里對應圖1所示的結構介紹二項佇列具有的性質和特點，
(1)二項樹，觀察圖1中的四棵樹，若不考慮節點數值的因素，可以看出樹2是由兩個樹1拼湊而成的，其中一個樹1結構充當另外一個樹1的右子樹，觀察樹3同樣也是如此，是一顆樹2充當了另外一顆樹2的右子樹生成而來，同理可見樹4，依據上述規律所生成的樹都稱為二項樹，樹1，樹2，樹3，樹4均是二項樹，根據二項樹的生成規律，不難知道高度為i的二項樹的結構是固定的，其節點總數為2^(i-1)個，
(2)二項佇列從結構上來說是由高度不重復的若干個二項樹構成的森林，高度不重復意味著相同高度的二項樹在二項佇列中最多存在一個，這里特別要注意二項佇列中的二項樹的高度不強制是連續的，比如高度為2的二項樹不存在，高度為5的二項樹卻存在，
其實也很好理解，二項佇列總節點數15，表示為二進制就是1111，二項樹的節點數正好符合二進制上每位的權值，
二丶二項佇列的“堆序性”
假如一個森林，僅僅滿足了上述的結構性，那它也還不是二項佇列，畢竟二項佇列是優先佇列的一種實作，無論如何也是需要具備和二叉堆和左式堆一樣的堆序性質的，同樣借助圖1來介紹二項佇列所具備的”堆序性質”，
(1)組成二項佇列的所有二項樹都具有一致的堆序性，每一個二項樹不僅僅滿足堆序性，而且每個二項樹的堆序性必須保持一致，要么都是大根堆，要么就是小根堆，
三丶二項佇列的建堆操作
合并操作是二項佇列中的核心操作，在合并操作的基礎上可以輕易的實作插入操作，因為插入操作可以理解為節點數為1的二項佇列的合并操作，而建堆操作則可以理解為一系列的插入操作，接下里利用圖例的形式來講解二項佇列的建堆操作，借用建堆的程序來清晰的闡述合并操作和插入操作，待建堆的操作如下，構建一個低優先級先出隊的二項佇列，
int[]A = new{5，4，3，2，1，9，7 }待建立二項佇列的陣列元素
(1)在實作二項佇列的合并操作之前，需要特別說明二項佇列的森林結構是利用一個節點陣列來存盤的，陣列當中的每一個節點都代表一個二項樹的根，對于節點數為N的二項佇列而言，其二項樹的個數可計算為Log(N)，對陣列大小的分配具體參加Log(N)，此處為了簡單陣列的大小分配為:Math.ceil(Log(N))+1=4，HeapNode [] item = new HeapNode[4]，HeapNode是二項樹節點定義，
如圖所示：
(2)對于陣列A而言，入隊第一個元素A[0] = 5，取二項佇列陣列的第一個元素item[0]，依據item[0]是否為空來采取后續措施，如下偽代碼所示，
if(item[0]==null)
item[0]= new HeapNode(A[0]);
else
merge(item[0],newHeapNode(A[0]));
依據如上的偽代碼此次執行的是if下的邏輯，入隊后結果如下：
圖4元素5入隊結果
(3)繼續入隊第二個元素A[1] = 4,同樣的取出二項佇列的第一元素item[0]，帶入步驟2的偽代碼邏輯，發現執行merge(item[0],newHeapNode[A[1]])邏輯，重點來了，此時執行的是merge(合并)邏輯，合并的物件是兩個只包含根節點的二項樹，將根節點較大的二項樹，充當根節點較小的二項樹的子樹，合并完成，結果如下
圖5元素4入隊結果
如圖5所示，原有的兩個二項樹合并成了一個新的二項樹，但是此時合并操作并沒有結束，新合并的二項樹不能存放在原有陣列的位置，其存放的陣列下標+1.調整結果如下，
圖6 元素4插入二項佇列的最終結果
(4)繼續入隊第三個元素3，重復步驟2，結果如圖7所示
圖7元素3插入二項佇列的最終結果
(5)繼續入隊第四個元素2，重復步驟2，發現Item[0]處存在元素，則重復步驟3，在步驟3中發現一個新問題，如下圖所示：
圖8 元素2入隊的中間結果
如上圖所示，元素2插入后需要和元素3進行合并，并且將合并的結果存到下標+1處即下標為1處，但是發現下標為1的地方以存在一個二項樹，此時需要繼續合并，將下標為1處的原二項樹和新合并產生的二項樹進行合并，合并結果如下：
圖9 元素2的入隊最終結果，
觀察圖9所示的結果，可以發現合并后高度為3的二項樹，同樣不存放在其原有的位置，而是存在其原有位置的下標+1處，其建立二項佇列操作介紹到此處，可以發現在二項佇列的陣列中，二項樹的高度和存盤位置的索引一一對應，高度為1的二項樹，存在下標為0處，高度為2的二項樹存在下標為1處，高度為3的二項樹存在下標為3處，依次類推高度為i的二項樹，存在下標為i-1處，
(6)繼續入隊第五個元素1，重復步驟2，入隊結果如下圖所示
圖10元素1的入隊結果
(7)繼續入隊第6個元素9，重復步驟2，結果如下：
圖11 元素9的入隊結果
(8)繼續入隊第7個元素7，重復步驟2.結果如下：
圖12元素7的入隊結果
依據上述的8個步驟，十分清晰的了解了二項佇列的建隊操作，為了進一步的加深對二項佇列的認識，下面來介紹一下二項佇列的合并操作，
四丶二項佇列的合并操作，
在上述的二項佇列建隊操作中，其實每一次插入操作都是特殊的合并操作，
都可以看成一個節點的二項佇列的特殊合并操作，二項佇列的合并程序其實用一句話就可以描述——將高度相同的二項樹合并，此處采用兩個簡單的二項佇列來闡述兩個二項佇列合并的具體實作程序，
圖13 待合并的兩個二項佇列
(1) 如圖13所示兩個待合并的二項佇列，在合并的程序中維護這一個指標i，i的初始值指向第一個元素i=0，這里假設合并的程序是h2并入h1的程序，分別取出h1和h2中第i個元素,發現h2對應的元素是null，不做處理,i++，結果如下，
圖14合并第一步
(2)和步驟1的處理相同，分別取出兩佇列中第i=1個位置的二項樹，均不為空，所以合并這兩個子樹，合并的結果存放到i+1=2處的位置，同時洗掉原佇列中第i=1個位置的二項樹，i++，在此程序中出現了沖突，第個i=2位置存在了二項樹，處理的方法和插入程序中處理合并的方法保持一致，合并結果如下：
圖15 合并第二步
(3)如圖15，此時i=2，兩個二項佇列分別取出第i個位置的二項樹，發現h1中為null，h2不為null，所以此時直接利用h2中的二項樹去覆寫h1中的第i個位置就行，然后洗掉h2中的二項樹，i++，結果如下圖所示，
圖16合并第三步，
(4)指標i移動完畢，該次合并結束，
五丶二項佇列的洗掉操作
在了解二項佇列的合并操作后，理解二項佇列的洗掉操作就十分簡單了，假設待洗掉二項佇列為H1，步驟如下：
- 遍歷H1中的陣列，找到根節點值最小的二項樹tree1，其根節點值就是出隊值，
2.從H1陣列中洗掉該二項樹tree1，將洗掉tree1后的二項佇列記為H2.
3.對于二項樹tree1，洗掉其根節點，利用其子樹d1，d2，d3….組成一個新的二項佇列H3，
4.合并H2和H3,合并后的二項佇列就是洗掉操作后的二項佇列，
在詳細的了解二項佇列建隊，洗掉，和插入操作后，可以給出二項佇列操作的時間復雜度(不做分析證明)，
1.合并操作的時間復雜度為LogN，
2.二項佇列洗掉操作中，找到具有最小根節點值的二項樹的時間消耗是O(logN)，合并兩個二項佇列的時間操作是Log(N)，洗掉操作的時間復雜度綜合起來也是Log(N)，
3.插入操作的時間復雜度是常數，這也是二項佇列優于左式堆的地方所在，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/69231.html
標籤：C
上一篇：演算法復雜度O(logn)詳解