Binomial Heaps: Merging Like Binary Addition

A binomial heap is a heap-based priority queue designed around one especially useful operation: merging two heaps efficiently. Its structure is built from binomial trees, and its merging process behaves much like binary addition. Two trees of the same degree are linked to create one tree of the next degree, just as two binary digits in the same position can produce a carry into the next position.

This relationship gives binomial heaps a clear connection between their forest structure and the binary representation of their size. A heap containing a certain number of nodes has at most one binomial tree of each degree, much like an integer has at most one 1 bit in each binary position. Inserting a single element resembles adding one to a binary number. Merging two heaps resembles adding two binary numbers. The links between trees represent the carries.

This article explains the heap invariant, binomial tree structure, insertion, merging, and extraction of the minimum. It also reviews ordinary binary heaps, including complete binary tree representation, heapify, sift-up, and sift-down, so the differences between binary heaps and binomial heaps are clear. Finally, it compares heaps with binary search trees and summarizes practical use cases and complexity.

What a heap guarantees​

A heap organizes elements according to priority. In a min-heap, the smallest key has the highest priority. In a max-heap, the largest key has the highest priority.

The central rule is the heap-order invariant:

• In a min-heap, every parent key is less than or equal to the keys of its children.
• In a max-heap, every parent key is greater than or equal to the keys of its children.

For example, this is a valid min-heap:

        3
      /   \\
     7     5
    / \\
   12    9

The root contains 3, and no child is smaller than its parent. The values do not need to be sorted from left to right. The 5 node appears to the right of 7, but that is not a problem. A heap constrains parent-child relationships, not the complete ordering of all nodes.

This invariant implies that the minimum of a min-heap is at its root if the heap has one tree. In a heap made of several trees, as a binomial heap is, the minimum must be at one of the roots. A descendant cannot be smaller than the root of its own tree.

The equivalent statement for a max-heap is that the maximum is at a root. Most structural operations work for both versions; only the comparison used to choose the preferred parent changes.

Complete binary trees and ordinary binary heaps​

Before examining binomial heaps, it helps to distinguish them from the more familiar binary heap. An ordinary binary heap is usually one complete binary tree.

A complete binary tree has every level completely filled except possibly the last, and nodes on the last level are filled from left to right. This shape allows the tree to be stored compactly in an array without explicit pointers.

With zero-based indexing, if a node is stored at index i, its children are commonly found at:

left child  = 2i + 1
right child = 2i + 2
parent      = floor((i - 1) / 2)

For example, the array

[3, 7, 5, 12, 9]

represents:

        3
      /   \\
     7     5
    / \\
   12    9

The array representation provides the shape invariant: the tree remains complete. Operations must preserve both shape and heap order.

A binary heap insertion appends a new item at the end of the array. Appending preserves completeness because the new node occupies the next left-to-right position. The new value might violate heap order with its parent, so the algorithm uses sift-up.

Binary heap extraction normally removes the root. To preserve completeness, the last array element moves into the root position, and the array shrinks by one. That replacement may violate heap order with its children, so the algorithm uses sift-down.

A binomial heap is different. It is a forest of binomial trees rather than one complete binary tree. Binomial trees are recursively defined and may have several children at their root. They are commonly represented using parent, child, and sibling pointers rather than an array. The word binomial therefore does not mean that the structure is simply an ordinary complete binary heap with a different name.

Heapify, sift-up, and sift-down​

These operations are especially important for ordinary binary heaps and help illustrate the general idea of preserving an invariant.

Sift-up​

Suppose a new value is appended to a min-heap. The shape is correct, but the new value may be smaller than its parent. Sift-up repeatedly compares the value with its parent and exchanges them while the heap-order rule is violated.

Starting with:

        4
      /   \\
     8     6
    /
   11

insert 2 at the next available position:

        4
      /   \\
     8     6
    / \\
   11    2

The 2 is smaller than its parent 8, so exchange them:

        4
      /   \\
     2     6
    / \\
   11    8

Now 2 is smaller than its parent 4, so exchange again:

        2
      /   \\
     4     6
    / \\
   11    8

The tree remains complete because the nodes never change positions in a way that violates the array shape. Each exchange moves the new item one level closer to the root. The height of a complete binary tree is logarithmic, so insertion takes O(log n) time in the worst case.

For a max-heap, the direction of the comparison is reversed. A newly inserted value moves upward while it is larger than its parent.

Sift-down​

For extraction from a binary min-heap, remove the root and move the last element to the root position. The shape remains complete, but the replacement may be larger than one of its children.

Suppose the heap is:

        2
      /   \\
     5     4
    / \\
   9     7

Remove 2 and move 7 to the root:

        7
      /   \\
     5     4
    /
   9

The 7 is larger than both children. To restore the invariant, exchange it with the smaller child, 4:

        4
      /   \\
     5     7
    /
   9

Now the heap order is restored. Sift-down must choose the smaller child in a min-heap. Choosing an arbitrary child could leave a smaller child below the replacement and fail to restore the invariant. In a max-heap, sift-down chooses the larger child.

Each exchange moves the replacement downward by one level. Since the height is O(log n), extraction takes O(log n) time.

Heapify​

Heapify converts an array or a tree that has the correct complete shape but not necessarily heap order into a valid binary heap. The bottom-up method starts at the last internal node and applies sift-down to each internal node while moving toward the root.

Leaves already satisfy heap order because they have no children. Internal nodes may violate it, so they are repaired after their subtrees have already been repaired. This bottom-up organization gives the standard build-heap operation a total time of O(n), not O(n log n).

The reason is that most nodes are near the leaves and can move only a small distance. Only a few nodes near the root can move many levels. The total work across all sift-down operations is linear.

Heapify is not the central operation in a binomial heap. A binomial heap is built by maintaining a forest of recursively structured trees and linking equal-degree trees. Still, heapify, sift-up, and sift-down illustrate a general principle: an operation can temporarily violate heap order, then repair only the path or set of structures affected by the change.

Binomial trees​

A binomial tree of degree 0, written B0, consists of one node:

B0:

    x

A binomial tree of degree 1, B1, is formed by linking two B0 trees. One root becomes the parent of the other:

B1:

    x
    |
    y

A binomial tree of degree 2, B2, is formed by linking two B1 trees. The root of one tree becomes a child of the root of the other. A representation using child and sibling pointers might draw it as:

B2:

        x
      /   \\
     a     b
     |
     c

The precise drawing depends on child-list order, but the important facts are consistent. A binomial tree Bk has:

• 2^k nodes;
• degree k at its root;
• height k;
• subtrees of the root corresponding to B0, B1, through B(k-1) in an appropriate order.

The node count explains the connection with binary arithmetic. B0 has 1 = 2^0 node, B1 has 2 = 2^1, B2 has 4 = 2^2, and B3 has 8 = 2^3.

A binomial tree is not necessarily a complete binary tree in the array-based sense. Its shape is defined recursively by linking equal-degree binomial trees. Its root may have several children, and pointer-based representations are natural for it.

The binomial heap invariant​

A binomial heap is a collection, or forest, of heap-ordered binomial trees with at most one tree of each degree.

The invariant has two parts:

1. Heap order: Each tree obeys min-heap order or max-heap order.
2. Unique degrees: The root list contains at most one Bk tree for every degree k.

For a min-binomial heap, the root of each tree is the smallest key in that tree. Therefore, the minimum key in the complete heap must be among the roots in the root list.

Consider a heap containing 13 nodes. Since

13 = 8 + 4 + 1

and 13 in binary is 1101, its forest can contain one B3 tree, one B2 tree, and one B0 tree:

B3, B2, B0

The root list is commonly maintained in increasing degree order, although the exact list convention is an implementation choice. The binary representation tells us which degrees are present. A heap with n nodes has at most floor(log2(n)) + 1 roots.

The unique-degree rule is what makes union special. If two heaps both contain a tree of degree k, those trees cannot remain separate after a valid merge. They must be linked into one tree of degree k + 1, possibly causing another collision at the next degree. This chain is the tree-level version of carrying in binary addition.

Linking two binomial trees​

The basic operation in binomial heap merging is linking two binomial trees of the same degree.

Suppose two B2 trees have roots with keys 4 and 9 in a min-heap. Since 4 is smaller, the root containing 4 remains the root, and the root containing 9 becomes a child of it. The result is a B3 tree:

Before:

Tree A, root 4       Tree B, root 9
      4                    9
    /   \\                /   \\
   ...  ...             ...  ...

After linking:

          4
       /  |  \\
      ... ...  9
              / \\
             ... ...

Two properties are preserved:

• The resulting tree has twice as many nodes, so two Bk trees become one B(k+1) tree.
• The preferred root remains above the other root, so heap order is preserved.

For a max-binomial heap, the larger root becomes the parent instead.

A link takes O(1) time when the implementation stores the needed pointers. It does not scan every node in either tree. Linking changes the relationship between the two roots and updates a small number of references.

Conceptually, min-heap linking is:

link(x, y):
    if x.key <= y.key:
        make y a child of x
        increase x.degree
        return x
    else:
        make x a child of y
        increase y.degree
        return y

The two input trees must have the same degree. The comparison abstraction can be reversed to support max-heaps.

Why merging resembles binary addition​

Each degree represents a binary position:

• A B0 tree represents a 1 in the 2^0 position.
• A B1 tree represents a 1 in the 2^1 position.
• A B2 tree represents a 1 in the 2^2 position.
• More generally, a Bk tree represents 2^k nodes.

Because there is at most one tree of each degree, every degree is either present or absent. That is exactly the pattern of binary bits.

Suppose one heap has 5 nodes. Its binary form is 101, so its forest contains:

B2 and B0

Suppose another heap has 3 nodes. Its binary form is 11, so its forest contains:

B1 and B0

The node total is 5 + 3 = 8, or binary 1000. At the tree level:

1. The two B0 trees collide and link into a B1 tree.
2. The existing B1 from the second heap collides with the new B1.
3. Those two B1 trees link into a B2 tree.
4. The new B2 collides with the existing B2 from the first heap.
5. The two B2 trees link into a B3 tree.

The final forest contains one B3, representing 8 nodes. The links are binary carries.

The keys decide which root wins each link, but the degrees and carry pattern are controlled by the node counts. This separation is useful: binary arithmetic explains the shape, while heap order explains parent selection.

Merging two binomial heaps​

The merge, also called union, operation combines two binomial heaps into one valid binomial heap.

It has two conceptual stages:

1. Combine the root lists by degree, like merging two sorted lists.
2. Scan the combined list and link trees whenever equal degrees collide.

Assume both root lists are sorted by increasing degree. The first stage is similar to the merge step of merge sort, except that degree rather than key determines list order.

For example, suppose one heap has roots of degrees 0 and 2, while the other has roots of degrees 1 and 2:

Heap A: B0, B2
Heap B: B1, B2

Combining the lists gives:

B0, B1, B2, B2

The two B2 trees must be linked:

B0, B1, B3

If the resulting B3 collides with another B3, the scan continues and links those trees too.

A simplified algorithm is:

UNION(H1, H2)
    combine the root lists in degree order
    scan the combined list from low degree to high degree

    whenever two trees have the same degree
        link them
        replace them with the resulting tree of degree + 1

    return the resulting root list

A careful implementation must handle a temporary run of three trees with the same degree. For example, after two lower-degree trees are linked, their carry may meet a tree already present at the next degree. One pair is linked, producing a higher-degree tree, while the remaining tree stays available for the next comparison. Pointer updates and scan advancement must be designed so that no tree is skipped.

The time complexity of union is O(log n) when n is the total number of nodes. Each heap has only logarithmically many roots, and the carry process moves toward larger degrees. If the analysis uses the number of roots directly, the work is linear in the number of roots.

Insertion: adding a singleton tree​

Insertion can be understood as creating a new B0 tree and merging it with the existing heap.

To insert key 6, begin with:

B0:

6

If the heap has no B0, add the tree to the root list. If a B0 already exists, link the two trees into a B1. If a B1 already exists, continue the carry.

Suppose an existing heap contains 7 nodes. Since 7 is binary 111, its forest contains B2, B1, and B0. Inserting one node increases the count to 8, binary 1000:

Existing: B2, B1, B0
New:             B0

B0 + B0 -> B1
B1 + B1 -> B2
B2 + B2 -> B3

Result: B3

Thus, a single insertion can trigger several links, just as adding 1 to a binary number can produce several carries.

A direct implementation can be expressed as:

INSERT(H, x)
    create a new heap Hx containing one B0 tree with key x
    return UNION(H, Hx)

The worst-case time is O(log n). The new tree may carry through every existing degree. Each individual link is constant time, and there are at most logarithmically many degrees.

The invariant is preserved at every stage. The root comparison preserves heap order, while repeated linking removes duplicate degrees.

Finding the minimum​

In a min-binomial heap, the minimum element must be at the root of one of the binomial trees. A child cannot be smaller than its root, so it is sufficient to scan the root list.

If there are r roots, the scan takes O(r) time. Since r is at most logarithmic in the number of nodes, straightforward FIND-MIN takes O(log n) time.

An implementation may maintain a direct pointer to the minimum root, making FIND-MIN O(1). That pointer must be updated when roots are added, linked, removed, or combined. It is an optional convenience, not a change to the binomial heap invariant.

For example, if the roots are:

B0 root: 14
B2 root: 5
B4 root: 11

then 5 is the minimum. There is no need to inspect the descendants of 14 or 11.

For a max-binomial heap, scan for the largest root or maintain a pointer to it.

Extract-min​

The extract-min operation removes and returns the smallest key from a min-binomial heap. It consists of several structural steps:

1. Find the root containing the minimum key.
2. Remove that root from the root list.
3. Turn its children into separate binomial trees.
4. Merge those trees with the remaining heap.
5. Link equal-degree trees until the unique-degree rule is restored.

Suppose the minimum root belongs to a B3 tree. Removing the root exposes child subtrees whose sizes correspond to B2, B1, and B0:

Before:

          m
       /  |  \\
     B2   B1  B0

After removing m, the children become separate roots:

B2, B1, B0

Each child subtree was already a valid binomial tree and already satisfied heap order internally. The removed root is the only node being discarded. The new root list may contain duplicate degrees when combined with the original remaining heap, so union performs the necessary links.

Conceptually:

EXTRACT-MIN(H)
    find root m with the smallest key
    remove m from H's root list

    create heap C from m's children
    clear the parent pointer of every child in C

    H = UNION(H, C)
    return m.key

The removed root of a Bk tree has k children, so it contributes at most O(log n) trees. Finding the minimum scans at most O(log n) roots, and union also takes logarithmic time. Therefore, standard extract-min takes O(log n) time.

For a max-binomial heap, the corresponding operation is extract-max. The procedure removes the root with the largest key and uses max-heap comparisons during linking.

Min-heaps versus max-heaps​

The shape rules of a binomial heap are the same for minimum and maximum priority queues. Only the priority comparison changes.

For a min-heap:

if rootA.key <= rootB.key
    rootA remains parent
else
    rootB remains parent

For a max-heap:

if rootA.key >= rootB.key
    rootA remains parent
else
    rootB remains parent

A useful implementation technique is to define a comparison such as higherPriority(a, b). For a min-heap, it returns true when a is smaller. For a max-heap, it returns true when a is larger. The linking, root scanning, and extraction code can then share the same structure.

Duplicate keys are normally permitted. When two equal roots are linked, either root may remain the parent as long as heap order is defined using less-than-or-equal or greater-than-or-equal consistently. If an application needs stable priority behavior, it must store an additional tie-breaking value, such as an insertion sequence number.

Pointer representation​

A binomial heap is commonly represented with linked pointers. A node may store:

• its key or priority;
• a pointer to its parent;
• a pointer to its first child;
• a pointer to its next sibling;
• its degree.

The first-child/next-sibling representation allows a node with several children to be represented compactly. The children form a linked list instead of fixed left and right child fields.

The root list links the roots of all binomial trees. Keeping roots ordered by degree makes union easier because two lists can be combined in degree order before the carry scan.

When one root becomes a child of another, the implementation must update the child root's parent pointer, connect it to the new parent's child list, and increase the new parent's degree. When a root is removed during extract-min, its children must be detached and their parent pointers cleared before they become roots of the auxiliary heap.

Child order may differ between implementations. Some store children from larger degree to smaller degree; others use the opposite direction. The algorithm should not depend on a particular visual order unless that order is deliberately maintained. The essential requirements are correct degrees, valid parent and sibling links, and heap order.

Complexity summary​

For a standard pointer-based binomial heap with a root list ordered by degree, typical bounds are:

The logarithmic bounds come from the fact that a Bk tree contains 2^k nodes. A heap with n nodes cannot have a tree degree larger than approximately log2(n), and it has at most one root at each degree.

For comparison, a conventional array-based binary heap usually provides:

The important distinction is union. Binomial heaps make union a direct logarithmic operation, while combining ordinary binary heaps is not usually a similarly simple operation in their standard array representation.

Binomial heaps versus binary search trees​

A binary search tree organizes values by range. For a node with key x, values in the left subtree are generally smaller than x, and values in the right subtree are generally larger. This global ordering supports searches for arbitrary keys, predecessor and successor queries, and sorted traversal.

A binomial heap has no equivalent left-versus-right ordering. It guarantees only parent-to-child priority order. If a min-heap contains a root 3 with children 10 and 5, the 5 can appear before or after 10 in the child list. The heap remains valid.

This leads to different strengths:

• A heap exposes the minimum or maximum efficiently.
• A search tree can search for an arbitrary key using ordering.
• A heap is not generally efficient for arbitrary-value lookup.
• A search tree supports ordered traversal; a heap traversal is not sorted.
• A binomial heap is specialized for priority queues and heap union.

Choosing between them depends on operations, not simply on the number of elements.

Priority queues and heap sort​

A priority queue repeatedly inserts items and removes the item with the highest priority. In a min-priority queue, the smallest key is removed first. Common abstract examples include selecting the next task, processing events by priority, and repeatedly choosing the smallest candidate in an algorithm.

Both binary heaps and binomial heaps can implement priority queues. A binary heap is often attractive because it is compact and array-based. A binomial heap is attractive when independently maintained priority queues need to be merged repeatedly. Its forest structure makes that operation explicit: combine root lists, then resolve equal-degree collisions through links.

Heaps are also associated with heap sort. A binary heap can support O(n log n) sorting by building a heap and repeatedly extracting the extreme element. Its complete-tree array representation is convenient for this purpose. A binomial heap can likewise support repeated insertion and extraction, but its distinctive purpose is efficient union rather than compact in-place sorting.

A practical choice follows the workload:

• Choose a binary heap when compact storage and simple array operations are important.
• Consider a binomial heap when merging priority queues is a central operation.
• Choose a search tree when arbitrary-key search and ordered iteration are required.

The data structure should match the operations that dominate the application.

A worked merge example​

Consider two min-binomial heaps. The first has 6 nodes. Since 6 is binary 110, its forest contains:

B2 and B1

The second has 5 nodes. Since 5 is binary 101, its forest contains:

B2 and B0

The combined degree list is:

B0, B1, B2, B2

The two B2 trees collide. Suppose their roots are 4 and 8. The root 4 remains above 8, producing a B3 tree. The resulting forest is:

B0, B1, B3

The node count is 1 + 2 + 8 = 11, matching 6 + 5 = 11. Binary addition shows the same result:

  110
+ 101
-----
 1011

The result has bits for B3, B1, and B0.

The keys determine which root becomes the parent during each link. The degree pattern is determined by the node counts and carries. Keeping those two roles separate makes the algorithm easier to reason about.

Common implementation mistakes​

Leaving duplicate degrees​

Concatenating two root lists is not enough. Equal-degree trees must be linked until no degree appears more than once. A root list containing two B2 trees violates the binomial heap invariant.

Linking different degrees​

The basic link operation is valid only for two trees of the same degree. Linking a B1 and a B2 does not produce a standard binomial tree.

Choosing the wrong parent​

In a min-heap, the smaller root must remain the parent. In a max-heap, the larger root must remain the parent. Reversing the comparison breaks heap order immediately.

Mishandling carries​

After linking two trees of degree k, the result is degree k + 1. It may collide with an existing tree of that degree. The scan must continue rather than treating the new tree as permanently placed.

Forgetting parent pointers​

When a root becomes a child, its parent pointer must be updated. When children are promoted during extract-min, their parent pointers must be cleared.

Losing children during extraction​

Removing a minimum root must preserve all child subtrees. Each child becomes a root in an auxiliary heap. Dropping or incorrectly reconnecting one of them loses nodes or creates invalid structure.

Assuming roots are sorted by key​

The root list is normally ordered by degree, not by key. The smallest root is not necessarily the first root unless a separate minimum pointer or a key-ordered root list is deliberately maintained.

Confusing heap order with sorted order​

A valid heap is not a sorted tree. Only the relationship between a parent and its descendants is guaranteed. A priority queue can remove the next extreme item efficiently without supporting arbitrary sorted traversal.

Testing a binomial heap​

A useful test suite should check both returned values and internal structure.

For heap order, recursively verify that every node satisfies the selected comparison with each child. For a min-heap, no child may have a smaller key than its parent.

For degree correctness, verify that a tree recorded as degree k contains 2^k nodes and that its root has the expected number of children. This may be too expensive for normal production operation, but it is valuable as a debugging assertion.

For the root-list invariant, verify that root degrees are ordered as required and that no degree is repeated. Count all nodes across all trees and compare the result with the recorded heap size.

Important behavioral tests include:

1. Insert into an empty heap.
2. Insert values that cause no carry.
3. Insert values that cause a long carry chain.
4. Merge heaps with no overlapping degrees.
5. Merge heaps with one degree collision.
6. Merge heaps that carry across several degrees.
7. Extract the minimum from a heap containing one tree.
8. Extract the minimum when several root trees remain.
9. Handle duplicate keys.
10. Repeatedly extract until the heap is empty and verify nondecreasing output.

Repeated extraction is a strong end-to-end test because it exercises root selection, child promotion, linking, pointer updates, and heap order together.

Practical takeaways​

A binomial heap is best understood as a binary number represented by trees:

• Each Bk tree contains 2^k nodes.
• A heap contains at most one tree of each degree.
• The forest's tree degrees correspond to the 1 bits of the heap's size.
• Linking two equal-degree trees is a binary carry.
• In a min-heap, the smaller root becomes the parent.
• In a max-heap, the larger root becomes the parent.
• Insertion is the union of the heap with a one-node B0 heap.
• Extract-min removes the minimum root, promotes its children, and unions the resulting forest back into the heap.
• Union takes logarithmic time because the number of possible root degrees is logarithmic.

The most important distinction from an array-based binary heap is structural. A binary heap is one complete binary tree, commonly stored in an array. Its insertion and extraction operations preserve completeness with append-and-sift-up and replace-and-sift-down. A binomial heap is a forest of recursively defined trees, commonly stored with pointers. Its insertion and merge operations preserve the unique-degree rule through tree links.

The binary-addition perspective makes the central algorithm memorable. A tree of degree k represents one occupied binary position. When two trees occupy the same position, they cannot both remain there, so they merge and carry into the next position. The comparison of their roots preserves heap order, while the carry process preserves the forest structure. Together, these two rules define the binomial heap.