Overview
A binomial heap stores heap-ordered binomial trees with at most one tree of each rank. Merge works like binary addition by linking trees of equal rank.
CoreSource checked
Binomial Heap
Maintains a mergeable priority queue as a forest of binomial trees.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Priority Queues
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
priority queue operationspriority queuesheap orderdata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use when meld is a required priority-queue operation.
- Use when a pointer-based heap with predictable logarithmic bounds is acceptable.
When Not to Use
- Avoid when a binary heap is simpler and meld is not needed.
- Avoid when pointer-heavy structures are too costly for the runtime environment.
What It Does
- Stores items across heap-ordered binomial trees
- Links equal-rank trees during merge
- Supports efficient meld, insert, and extract-min operations
Use Cases
- Priority queues that need fast melding
- Graph algorithms with many heap merges
- Teaching mergeable heap structure
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.Merge root lists by increasing rank
- 2.Scan roots while carrying linked trees of equal rank
- 3.When two equal-rank trees collide, link the larger root under the smaller root
- 4.Keep at most one root of each rank
- 5.For extract-min, remove the smallest root and meld its children back
Canonical Example
- Input
- meld heaps with rank-0 roots 3 and 5
- Output
- one rank-1 tree rooted at 3
- Explanation
- The smaller root becomes parent when two equal-rank binomial trees are linked.
Implementation Notes
- Represent root lists sorted by rank.
- Implement meld first, then define insert as meld with a one-node heap.
- Test carry chains where several equal-rank trees link in sequence.
Common Pitfalls
- Allowing two roots of the same rank breaks the binomial-heap invariant.
- Linking roots in the wrong order violates heap ordering.
- Extract-min must reverse or merge the removed root's children correctly.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow storing heap-ordered binomial trees whose sizes follow binary representation on a small priority queue operations example.
Step 1 of 5: Merge root lists by increasing rank
data-structures-mechanismNotes
Binomial heaps are easiest to reason about when meld is treated as the central operation.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookReference for Binomial Heap binomial tree merging, heap union, and priority-queue operations.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toHeap
Data Structures · Foundation
Binomial heaps support efficient melding, while array heaps are simpler for nonmeld workloads.
Compare with thisAlternativesLeftist Heap
Data Structures · Core
Both support melding, but maintain different structural invariants.
Compare with thisRelationships
View full relationship pageAlternative toHeap
Binomial heaps support efficient melding, while array heaps are simpler for nonmeld workloads.
Conceptual neighborFibonacci Heap
Fibonacci heaps relax binomial-heap consolidation to improve amortized bounds.
Alternative toPairing Heap
Pairing heaps are another pointer-based mergeable heap design.
Related Algorithms
Tags
Data StructurePriority Queue