Binomial Heap Meld Carries
Meld heap forests by linking equal degrees like carries in binary addition.
Free theory articleMeld heap forests by linking equal degrees like carries in binary addition.
Concept & interpretation
A binomial heap is implemented as a collection of binomial trees (a forest). Each binomial tree of order k has 2k 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.
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.