二項式堆積

在計算機科學中，二項堆（英語：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.