Binomial Heap Meld Carries

A binomial heap is implemented as a collection of binomial trees (a forest). Each binomial tree of order k has 2^k nodes, and its root has degree k. When melding two binomial heaps, we combine the root lists much like adding two binary numbers, where linking two trees of degree k creates a "carry" tree of degree k+1.

Worked Example: Melding two small forests

Consider Heap A with elements [4, 2, 8, 3] (Prefix A: 4) and Heap B with elements [5, 5, 1] (Prefix B: 3).

Heap A construction: Insert 4, then 2 (meld 4 and 2 into degree 1 tree with root 2), then 8, then 3 (meld 8 and 3 into degree 1 tree with root 3, then meld with degree 1 tree to get degree 2 tree with root 2). Total size is 4. Binary representation of 4 is 100, so we have one tree of degree 2.
Heap B construction: Insert 5, then 5 (meld 5 and 5 into degree 1 tree with root 5, tie broken by insert order ID), then 1. Total size is 3. Binary representation of 3 is 011, so we have trees of degree 0 (root 1) and degree 1 (root 5).
Melding A and B: We align trees by degree.
- Degree 0: Only Heap B has degree 0 (root 1).
- Degree 1: Only Heap B has degree 1 (root 5).
- Degree 2: Only Heap A has degree 2 (root 2).
There are no collisions during the meld (no equal degree roots to link). Thus, the meld requires 0 links. The resulting heap has size 7 (binary 111), with root degrees 0, 1, 2 and root keys 1, 5, 2. The minimum key is 1. The total links for construction are 4 (3 for A + 1 for B), and 0 for meld, making total 4.

Interactive Experiment

You can verify these properties using the Binomial Heap Meld Carries explorer.

Select Heap A: Long and Prefix A: 4 to build a forest with nodes 4, 2, 8, 3.
Select Heap B: Ties and Prefix B: 3 to build a forest with nodes 5, 5, 1.
Observe that the final Heap size is 7, the Root degrees are 0,1,2, and the Total links is 4.
Change Heap A: Short and Heap B: Pair to see collisions causing carries during the meld, resulting in additional Meld links.

Limitations

This module visualizes standard binomial heap melding (binary carries). It supports a small, finite set of inputs to clearly show the carries. It does not implement decrease-key or delete operations, and does not model lazy Fibonacci heap bounds where the amortized cost differs. The maximum input size is intentionally bounded to fit the visual canvas. Real-world implementations may use pointers and lazy melding depending on the specific priority queue variant.

References

The tree melding logic is modeled after standard binomial queues. For the formal algorithms, structural properties and performance analysis, see the lecture notes: Introductory Algorithms - Binomial Heaps (Johns Hopkins University).

Binomial Heap Meld Carries