---

Binomial Heaps — Detailed Explanation

A Binomial Heap is a type of priority queue data structure that supports fast merging (union) of two heaps.
It is built using a collection of Binomial Trees, not just a single tree.

It is used where merge operations are very frequent, such as in network optimization algorithms and job scheduling.

---

1. What is a Binomial Tree?

A Binomial Tree ( B_k ) of order k has the following properties:

1. ( B_0 ) is a single node.
2. ( B_k ) is formed by linking two ( B_{k-1} ) trees, making one the leftmost child of the other.
3. It has exactly ( 2^k ) nodes.
4. Height of the tree = k.
5. It has k choose i nodes at depth i.
6. Structure is fixed → no shape changes.

Example:

• B0 → 1 node
• B1 → 2 nodes
• B2 → 4 nodes
• B3 → 8 nodes

---

2. What is a Binomial Heap?

A Binomial Heap is a set (collection) of Binomial Trees that satisfies:

1. Min-heap property:
   The key of a node ≥ key of its parent.
2. At most one binomial tree of any order k
   Means the heap resembles binary representation of a number.

For example:
If n = 13 → binary = 1101
It has trees of order:

• B0
• B2
• B3

---

3. Structure of a Binomial Heap

A binomial heap H consists of a list of binomial trees sorted by increasing order of degree:

H = B0, B2, B3

Example diagram of Binomial Trees inside a heap:

B0     B2           B3
·      ·-·          ·-·
      / \         / |  \
     ·   ·      ·  ·   ·
                / \
               ·   ·

---

4. Operations on Binomial Heap

A. Create / Make-Heap

Creates an empty heap.

---

B. Find Minimum

Simply search roots of all binomial trees (because each tree’s root is minimum of that tree).

Time = O(log n)
(There are at most log n trees.)

---

C. Union / Merge (Most Important Operation)

This is where Binomial Heaps excel.

Steps:

1. Merge root lists of both heaps (like merge of two linked lists).
2. Combine trees of the same order (like binary addition with carry):
   • If two trees of same degree k exist → link them to form ( B_{k+1} ).

Time Complexity = O(log n)
(At most one merge per degree like binary addition.)

---

D. Insertion of Key

To insert a key X:

1. Create a heap containing a single node (a B0 tree).
2. Union it with the existing heap.

Time = O(log n)

---

E. Delete Minimum

Steps:

1. Find min root.
2. Remove its Binomial Tree.
3. Remove the root of this tree.
4. Reverse the order of its children (to convert them into a valid heap).
5. Union the resulting heap with original heap.

Time = O(log n)

---

F. Decrease Key

1. Decrease the key.
2. Bubble up by swapping with parent until heap property holds.

Time = O(log n)

---

G. Delete a Node

1. Decrease key to (-\infty)
2. Now it becomes minimum.
3. Call delete-min.

Time = O(log n)

---

5. Time Complexities Summary

Operation	Time
Make-heap	O(1)
Find-min	O(log n)
Insert	O(log n)
Delete-min	O(log n)
Decrease-key	O(log n)
Merge two heaps	O(log n)
Delete	O(log n)

Merging efficiency makes Binomial Heaps extremely useful.

---

6. Applications of Binomial Heaps

Binomial Heaps are used in:

• Implementing priority queues
• Graph algorithms like:
  • Prim’s Minimum Spanning Tree
  • Dijkstra’s shortest path (alternate to Fibonacci heaps)
• Scheduling tasks
• Multilevel memory management
• Any domain where merge operation is very frequent

---

7. Binomial Heap vs Binary Heap vs Fibonacci Heap

Feature	Binomial Heap	Binary Heap	Fibonacci Heap
Structure	Collection of binomial trees	Single binary tree	Collection of trees
Merge	Fast (O(log n))	Slow (O(n))	Very fast (O(1))
Decrease-key	O(log n)	O(log n)	O(1)
Implementation	Moderate	Easy	Very complex
Applications	Merge-heavy scenarios	Simple priority queue	High-performance graph algorithms

---

Summary

A Binomial Heap:

• Is a collection of binomial trees
• Supports fast merge operation
• Most operations take O(log n)
• Extensively used in priority queues, MST algorithms, and problems requiring frequent merging

---