What is a binomial heap?

A binomial heap is a group of binomial trees. This data structure acts as a priority queue and implements the merge operation faster.

The binomial heap data structure should satisfy the following two properties:

• All trees in the binomial heap should obey the min-heap property. The min-heap property states that the key of a node should be greater than or equal to the parent node key.
• One binomial tree exists for each order. This means that for each k, there will be at most one binomial tree of order k in the binomial heap.

Binomial trees

A binomial tree is a data structure that satisfies the properties listed below:

• • A binomial tree of order 0 has only one node.
  • If a binomial tree has order m, the tree will have exactly 2^m This implies that it is possible to construct a binomial tree of order m, using two binomial trees having order m-1 and by making one of them the left-most child.
  • The root of the binomial tree has degree m, and the children of the root are themselves binomial trees of order m-1, m-2, ..., 1, 0 from left to right.

Binomial heap example 

Consider the following example to understand binomial heap:

The figure below shows a binomial heap containing 13 nodes.

Each node in the tree obeys the min-heap property in its binomial tree. Element 12 is the smallest element and the root of the tree of order 3. Similarly, 5 is the smallest element and root of the binomial tree of order 2. 9 is the root of the binomial tree of order 0. All these binomial trees are merged to generate a binomial heap containing 13 nodes.

Operations on a binomial heap

The following operations are possible on a binomial heap:

• Merge or union
• Insert node
• Find minimum key
• Delete minimum key
• Decrease key
• Delete node

Merge/union of two binomial heaps

The union operation combines two binomial heaps having the same order. The process to combine two binomial heaps is as follows:

• Combine the binomial heaps in increasing order of their degrees.
• After combining the trees, ensure there is a maximum of one binomial tree of any order. Now, begin combining the trees having the same order.
• Use three-pointers to traverse the list: previous, x, and next-x. Use the following four cases for traversing:

Case 1: If order[x] ≠ order[next-x], move the pointer ahead.

Case 2: If order[x] = order[next-x] = order[sibling(next-x)], move the pointer ahead.

Case 3: If order[x] = order[next-x] ≠ order[sibling(next-x)], and

Case 4: If order[x] = order[next-x] ≠ order[sibling(next-x)], and key[x] > key[next-x], remove x from root and link it to [next-x].

Time complexity: The time complexity for union operation on two binomial heaps is O(log n).

Insert node in a binomial heap

The insertion operation inserts a new element to the binomial heap. It first creates a new heap containing the new element then merges it with the original heap.

In other terms, the insert operation works as follows:

• Insert(H, k) will make a new binomial heap H1 and add element k into it.
• The operation will now call a union operation to merge the binomial heap H1 with the existing binomial heap H.

Time complexity: The insert operation takes O(log n) time for execution due to the merge operation. However, each successive insert takes an amortized time of O(1) per insertion.

Find minimum key

This operation looks for the minimum element in the binomial heap. The operation finds the minimum element of the heap by first finding the minimum key among the binomial tree roots. This means the getMin() function first traverses through the list of the binomial tree roots, then returns the minimum element in the binomial heap.

Time complexity: The find minimum operation takes O(log n) time since it has to traverse through O(log n) roots in the binomial tree. However, this time can be reduced to O(1) by creating a pointer pointing to the minimum key root.

Delete the minimum key in a binomial heap

Delete/extract the minimum key operation is used to eliminate the element having the least value from the binomial heap. The operation works as follows:

• Search for the element having the least value in the binomial heap using the getMin() function.
• Eliminate it from the binomial tree root node.
• Get the list of the node’s child subtrees.
• Convert this list of subtrees into another binomial heap by joining the subtrees and reordering them in increasing order.
• Merge the new heap with the original heap using the union operation.

Time complexity: The extract minimum operation takes O(log n) time. Each root has at most log₂n children, so O(log n) time is needed to create the new heap. Then the merge operation takes O(log n) time. Consequently, the entire extract minimum operation requires O(log n) time.

Decrease key in a binomial heap

This function is used to reduce the key of an element. After reducing the key of the element, if the key becomes smaller than that of its parent, it will violate the min-heap property. If such a situation occurs, exchange it with its parent element (or even grandparent element, if required) until the min-heap property is fulfilled.

Time complexity: The decrease key operation takes O(log n) time since each binomial tree has at most height log₂n.

Delete the node in a binomial heap

To delete a node from the binomial heap, replace the key value with negative infinity (-∞), which means change it to a value lesser than any other heap element, then delete the minimum key in a heap using the extractMin() function.

Time complexity: The delete operation requires O(log n) time for execution.

Context and Applications

The binomial heap is an important topic in data structure and algorithms. The topic is taught in various courses like:

• Bachelor of Science in computer science
• Master of Science in computer science
• Bachelor of Science in information technology
• Master of Science in information technology

Practice Problems

Q1) Which property does the binomial heap data structure follow?

1. Min-heap 
2. Binomial heaps H1 algorithms binomial trees
3. Binomial-heap-merge binary heaps binomial trees
4. Binomial-heap-union algorithms

Answer: Option a

Explanation: The binomial heap data structure follows the min-heap property.

Q2) Which operation is used to combine two binomial heaps?

1. Binomial-heap-decrease-key-binomial-heap-merge binomial trees
2. Union
3. Iteration of the while loop binomial trees
4. Binomial-heap-minimum binomial trees_binomial-heap-union

Answer: Option b

Explanation: The Union operation is used to merge two binomial heaps.

Q3) What is the time complexity of delete node operation?

1. Binomial-heap-minimum binomial trees
2. Binomial tree Bk binary heaps_binomial-heap-merge
3. O(log n)
4. Binomial-heap-decrease-key binary heaps

Answer: Option c

Explanation: The time complexity of the delete node operation is O(log n)

Q4) How many nodes does a binomial tree of order 0 have?

1. Binomial-heap-union binomial trees
2. Binomial-heap-delete binomial trees
3. Binomial-heap-insert binomial trees
4. One 

Answer: Option d

Explanation: A binomial tree of order 0 can have only one node.

Q5) Which operation is used to delete the minimum key from the binomial heap?

1. Iteration of the while loop-binomial trees binomial-heap-extract-min
2. Binomial-heap-extract-min-binomial trees pointer
3. Make-binomial-heap-binomial trees pointer
4. Delete minimum key

Answer: Option d

Explanation: The delete minimum key operation is used to extract the minimum key from the binomial heap.

Common Mistakes

Students often consider the data structures binomial heap and binomial tree as the same. However, it is not true since they are two different concepts. Students should understand the difference between these data structures and not use the terms interchangeably.

Related Concepts

• Binary heaps
• Binary search tree
• Sparse tree
• Minimum-spanning-tree
• Hash table
• Heap data structure
• Binomial trees