二項式堆積

在電腦科學中，二項式堆積（英語：Binomial heap）是一種類似於二元堆積的堆結構。與二元堆積相比，其優勢是可以快速合併兩個堆，因此它屬於可合併堆（mergeable heap）抽象資料類型的一種。

二項樹

二項樹遞迴定義如下：

• 度數為0的二項樹只包含一個節點
• 度數為k的二項樹有一個根節點，根節點下有$k$個子女，每個子女分別是度數分別為$k-1,k-2,...,2,1,0$的二項樹的根

二項樹（從左至右度數分別為0至3

度數為k的二項樹共有$2^{k}$個節點，高度為$k$。在深度d處有${\tbinom {k}{d}}$（二項式係數）個節點。

度數為k的二項樹可以很容易從兩顆度數為k-1的二項樹合併得到：把一顆度數為k-1的二項樹作為另一顆原度數為k-1的二項樹的最左子樹。這一性質是二項式堆積用於堆合併的基礎。

二項式堆積

二項式堆積是指滿足以下性質的二項樹的集合：

• 每棵二項樹都滿足最小堆性質，即節點關鍵字大於等於其父節點的值
• 不能有兩棵或以上的二項樹有相同度數（包括度數為0）。換句話說，具有度數k的二項樹有0個或1個。

以上第一個性質保證了二項樹的根節點包含了最小的關鍵字。第二個性質則說明節點數為$n$的二項式堆積最多只有 $\log {n}$ 棵二項樹。實際上，包含n個節點的二項式堆積的構成情況，由n的二進制表示唯一確定，其中每一位對應於一顆二項樹。例如，13的二進制表示為1101, $2^{3}+2^{2}+2^{0}$, 因此具有13個節點的二項式堆積由度數為3, 2, 0的三棵二項樹組成：

範例：一個含13個節點的二項式堆積

二項式堆積的操作

由於並不需要對二項樹的根節點進行隨機存取，因而這些節點可以存成鏈結串列結構。

合併

合併分支度相同的二項樹

合併兩個二項式堆積範例，實際上把兩棵分支度為1的二項樹合併為一棵分支度為2的二項樹。

最基本的為二個分支度相同的二項樹的合併。由於二項樹根節點包含最小的關鍵字，因此在二棵樹合併時，只需比較二個根節點關鍵字的大小，其中含小關鍵字的節點成為結果樹的根節點，另一棵樹則變成結果樹的子樹。

function mergeTree(p, q)
    if p.root <= q.root
        return p.addSubTree(q)
    else
        return q.addSubTree(p)

兩個二項式堆積的合併則可按如下步驟進行：分支度$j$從小取到大，在兩個二項式堆積中如果其中只有一棵樹的分支度為$j$，即將此樹移動到結果堆，而如果只兩棵樹的分支度都為$j$，則根據以上方法合併為一個分支度為$j+1$的二項樹。此後這個分支度為$j+1$的樹將可能會和其他分支度為$j+1$的二項樹進行合併。因此，對於任何分支度j，可能最多需要合併3棵二項樹。

此操作的時間複雜度為${O}(\log n)$。

function merge(p, q)
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())
        
        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())
        
        heap.addTree(tree)
        heap.next(); p.next(); q.next()

插入

建立一個只包含要插入元素的二項式堆積，再將此堆與原先的二項式堆積進行合併，即可得到插入後的堆。由於需要合併，插入操作需要${O}(\log n)$的時間。平攤分析的時間複雜度為${O}(1)$。

尋找最小關鍵字所在節點

由於滿足最小堆性質，只需尋找二項樹的的根節點即可，因為一共有$\log n$棵子樹，所以用所時間為${O}(\log n)$。

可以儲存一個指向最小元素的指標，使得尋找最小關鍵字所在節點需要${O}(1)$的時間。在執行其他操作時，需要修改該指標。

刪除最小關鍵字所在節點

先找到最小關鍵字所在節點，然後將它從其所在的二項樹中刪除，並獲得其子樹。將這些子樹看作（合併為）一個獨立的二項式堆積，再將此堆合併到原先的堆中即可。由於每棵樹最多有$\log n$棵子樹，新增堆的時間為${O}(\log n)$。同時合併堆的時間也為${O}(\log n)$，故整個操作所需時間為${O}(\log n)$。

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

減小特定節點(關鍵字)的值(Decreasing a key)

在減小特定節點（關鍵字）的值後，可能會不滿足最小堆積性質。此時，將其所在節點與父節點交換，如還不滿足最小堆性質則再與祖父節點交換……直到最小堆性質得到滿足。操作所需時間為${O}(\log n)$。

刪除

將需要刪除的節點的關鍵字的值減小到負無窮大（比二項式堆積中的其他所有關鍵字的值都小即可），執行「減小關鍵字的值」演算法，使其調整到當前二項樹的根節點位置，再刪除最小關鍵字的根節點即可。

執行時間

以下對於二項式堆積操作的執行時間都為${O}(\log n)$（節點數為$n$）：

• 在二項式堆積中插入新節點
• 尋找最小關鍵字所在節點
• 從二項式堆積中刪除最小關鍵字所在節點
• 減小給定節點關鍵字的值
• 刪除給定節點
• 合併兩個二項式堆積

參見

• 斐波那契堆積

參考資料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein（潘金貴等譯）. 《算法导论》. 機械工業出版社. 
• Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309–314.

外部連結

• （英文）二項式堆積的Java applet摸擬
• （英文）二項式堆積的Python實現（頁面存檔備份，存於網際網路檔案館）
• （英文）二項式堆積的C實現（頁面存檔備份，存於網際網路檔案館）
• （英文）二項式堆積的Java實現