AntInLoop

Binomial Heap Data Structure Data Structure

A Binomial Heap is a mergeable priority queue composed of a forest of heap-ordered Binomial Trees mirroring the binary representation of n, supporting O(log n) merge and O(1) amortized insert.

OperationComplexity
AccessO(log n) / O(1) cached min
SearchO(n)
InsertionO(log n) worst / O(1) amortized
DeletionO(log n)
SpaceO(n)

Interactive Visualizer · C++ / Python / Java / JS Code

Binomial Heap Data Structure

A Binomial Heap is a mergeable priority queue built as a collection of heap-ordered Binomial Trees $B_0, B_1, B_2, \dots$, where $B_k$ has exactly $2^k$ nodes and is formed by linking two $B_{k-1}$ trees together. Just like binary addition of $n$, a Binomial Heap of size $n$ contains at most one $B_k$ for each set bit in the binary representation of $n$—allowing two entire heaps of size $n$ to be merged in $O(\log n)$ time (compared to $O(n)$ for a Binary Heap)!

At a Glance

| Operation | Binary Heap | Binomial Heap |

| :--- | :---: | :---: |

| findMin | $O(1)$ | $O(\log n)$ (or $O(1)$ with cached min ptr) |

| insert | $O(\log n)$ | $O(1)$ amortized / $O(\log n)$ worst |

| merge(H1, H2) | $O(n)$ | $O(\log n)$ |

| extractMin | $O(\log n)$ | $O(\log n)$ |

| decreaseKey | $O(\log n)$ | $O(\log n)$ |

---

How Merge Works (Literally Binary Addition!)

1. Merge the two root lists in increasing order of tree degree $k$.

2. Walk the merged root list: whenever two consecutive trees have the same degree $k$, link the one with the larger root key as the leftmost child of the smaller root—creating a single $B_{k+1}$ tree (just like carrying a bit in binary addition!).

---

Practice Problems

Easy

1. Binomial Heap Implementation (insert, merge, extractMin)

Implement a mergeable min-Binomial Heap supporting insert, merge, findMin, and extractMin in $O(\log n)$ time.

Approach: Represent each binomial tree with child / sibling pointers, implement linkTrees and mergeHeaps, and implement extractMin by reversing the minimum root's children into a new binomial heap and merging it back!

<details>

<summary>Show C++ Solution</summary>

#include <climits>
#include <iostream>
#include <utility>

struct BNode {
    int key, deg = 0;
    BNode *child = nullptr, *sibling = nullptr;
    explicit BNode(int k) : key(k) {}
};

BNode* linkTrees(BNode* a, BNode* b) {
    if (a->key > b->key) std::swap(a, b);
    b->sibling = a->child;
    a->child = b;
    ++a->deg;
    return a;
}

BNode* mergeRootLists(BNode* h1, BNode* h2) {
    BNode dummy(0);
    BNode* tail = &dummy;
    while (h1 && h2) {
        if (h1->deg <= h2->deg) { tail->sibling = h1; h1 = h1->sibling; }
        else { tail->sibling = h2; h2 = h2->sibling; }
        tail = tail->sibling;
    }
    tail->sibling = h1 ? h1 : h2;
    return dummy.sibling;
}

BNode* mergeHeaps(BNode* h1, BNode* h2) {
    BNode* head = mergeRootLists(h1, h2);
    if (!head) return nullptr;

    BNode *prev = nullptr, *cur = head, *nxt = cur->sibling;
    while (nxt) {
        if (cur->deg != nxt->deg || (nxt->sibling && nxt->sibling->deg == cur->deg)) {
            prev = cur;
            cur = nxt;
        } else {
            if (cur->key <= nxt->key) {
                cur->sibling = nxt->sibling;
                cur = linkTrees(cur, nxt);
            } else {
                if (!prev) head = nxt;
                else prev->sibling = nxt;
                cur = linkTrees(nxt, cur);
            }
        }
        nxt = cur->sibling;
    }
    return head;
}

BNode* insertHeap(BNode* head, int key) {
    return mergeHeaps(head, new BNode(key));
}

int extractMin(BNode*& head) {
    if (!head) return INT_MAX;
    BNode *minPrev = nullptr, *minNode = head, *prev = nullptr, *cur = head;
    while (cur) {
        if (cur->key < minNode->key) { minNode = cur; minPrev = prev; }
        prev = cur; cur = cur->sibling;
    }
    if (!minPrev) head = minNode->sibling;
    else minPrev->sibling = minNode->sibling;

    // Reverse children of minNode to form a valid binomial heap
    BNode *childRev = nullptr, *c = minNode->child;
    while (c) { BNode* nxt = c->sibling; c->sibling = childRev; childRev = c; c = nxt; }
    int res = minNode->key;
    delete minNode;
    head = mergeHeaps(head, childRev);
    return res;
}

int main() {
    BNode *h1 = nullptr, *h2 = nullptr;
    for (int x : {10, 4, 15}) h1 = insertHeap(h1, x);
    for (int x : {7, 2, 12}) h2 = insertHeap(h2, x);
    BNode* merged = mergeHeaps(h1, h2);
    while (merged) std::cout << extractMin(merged) << " ";
    std::cout << "\n"; // 2 4 7 10 12 15
    return 0;
}

</details>

---

Related Structures & Algorithms

  • Binary Heap — faster in practice when heap merging isn't required.
  • Fibonacci Heap — lazy binomial-like heap achieving $O(1)$ amortized merge and decreaseKey.