Python Program to Implement Binomial Heap

This is a Python program to implement a binomial heap.

Problem Description

The program creates a binomial min-heap and presents a menu to the user to perform various operations on it.

Problem Solution

1. Create a class BinomialTree with instance variables key, children and order. children is set to an empty list and order is set to 0 when an object is instantiated.
2. Define method add_at_end which takes a binomial tree of the same order as argument and adds it to the current tree, increasing its order by 1.
3. Create a class BinomialHeap with an instance variable trees set to an empty list. This list will contain the set of binomial trees.
4. Define methods get_min, extract_min, combine_roots, merge and insert.
5. The method get_min returns the minimum element in the heap by returning the key of the smallest root in the list trees.
6. The method merge takes a heap as argument and merges it with the current heap. It iterates through the sorted (by order of each tree) list of trees and merges any two trees with the same order. It also checks for the case for three consecutive trees of the same order and merges the last two trees.
7. The method combine_roots takes a heap as argument and combines the current heap’s list of trees with its list of trees and sorts them by order of each tree.
8. The method extract_min removes and returns the minimum element in the current heap. It does so by removing the tree with the smallest root from the current heap’s list of trees and creating a heap with the children of the smallest root as its list of trees. This new heap is then merged with the current heap.
9. The method insert takes a key as argument and adds a node with that key to the heap. It does so by creating an order 0 heap with that key and then merging it with the current heap.

Program/Source Code

Here is the source code of a Python program to implement a binomial heap. The program output is shown below.

```class BinomialTree:
def __init__(self, key):
self.key = key
self.children = []
self.order = 0

self.children.append(t)
self.order = self.order + 1

class BinomialHeap:
def __init__(self):
self.trees = []

def extract_min(self):
if self.trees == []:
return None
smallest_node = self.trees[0]
for tree in self.trees:
if tree.key < smallest_node.key:
smallest_node = tree
self.trees.remove(smallest_node)
h = BinomialHeap()
h.trees = smallest_node.children
self.merge(h)

return smallest_node.key

def get_min(self):
if self.trees == []:
return None
least = self.trees[0].key
for tree in self.trees:
if tree.key < least:
least = tree.key
return least

def combine_roots(self, h):
self.trees.extend(h.trees)
self.trees.sort(key=lambda tree: tree.order)

def merge(self, h):
self.combine_roots(h)
if self.trees == []:
return
i = 0
while i < len(self.trees) - 1:
current = self.trees[i]
after = self.trees[i + 1]
if current.order == after.order:
if (i + 1 < len(self.trees) - 1
and self.trees[i + 2].order == after.order):
after_after = self.trees[i + 2]
if after.key < after_after.key:
del self.trees[i + 2]
else:
del self.trees[i + 1]
else:
if current.key < after.key:
del self.trees[i + 1]
else:
del self.trees[i]
i = i + 1

def insert(self, key):
g = BinomialHeap()
g.trees.append(BinomialTree(key))
self.merge(g)

bheap = BinomialHeap()

print('insert <data>')
print('min get')
print('min extract')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
bheap.insert(data)
elif operation == 'min':
suboperation = do[1].strip().lower()
if suboperation == 'get':
print('Minimum value: {}'.format(bheap.get_min()))
elif suboperation == 'extract':
print('Minimum value removed: {}'.format(bheap.extract_min()))

elif operation == 'quit':
break```
Program Explanation

1. Create an instance of BinomialHeap.
2. The user is presented with a menu to perform various operations on the heap.
3. The corresponding methods are called to perform each operation.

Runtime Test Cases
```Case 1:
insert <data>
min get
min extract
quit
What would you like to do? insert 3
What would you like to do? insert 7
What would you like to do? insert 1
What would you like to do? insert 4
What would you like to do? min get
Minimum value: 1
What would you like to do? min extract
Minimum value removed: 1
What would you like to do? min extract
Minimum value removed: 3
What would you like to do? min extract
Minimum value removed: 4
What would you like to do? min extract
Minimum value removed: 7
What would you like to do? min extract
Minimum value removed: None
What would you like to do? quit

Case 2:
insert <data>
min get
min extract
quit
What would you like to do? insert 10
What would you like to do? insert 12
What would you like to do? insert 5
What would you like to do? insert 6
What would you like to do? min get
Minimum value: 5
What would you like to do? insert 3
What would you like to do? min get
Minimum value: 3
What would you like to do? insert 8
What would you like to do? min extract
Minimum value removed: 3
What would you like to do? min extract
Minimum value removed: 5
What would you like to do? insert 1
What would you like to do? min extract
Minimum value removed: 1
What would you like to do? quit```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!