Binary heap implementation in Python
Hi guys, today we have got the topic binary heap in Python language. So basically, what is a binary heap? It is a non-hierarchial tree-based data structure which is an almost complete tree.
A binary heap can be min-heap or max-heap. If the root element is the smallest of all the key elements present then the heap is min-heap. If the root element is greatest of all the key elements present then the heap is a max- heap.
Creating a Binary heap in Python
For creating a binary heap we need to first create a class. The instance variables or the objects of the class are set to an empty list to store the content of heap. Here is the code for implementation of the binary heap in Python:
class BinaryHeap: def __init__(self): self.heap = [] def left_child(self, i): return 2*i + 1 def right_child(self, i): return 2*i + 2 def Length(self): return len(self.heap) def Parent(self, i): return (i - 1)//2 def Get_Index(self, i): return self.heap[i] def get_max(self): if self.Length() == 0: return None return self.heap[0] def Extract_maximum(self): if self.Length() == 0: return None largest = self.get_max() self.heap[0] = self.heap[-1] del self.heap[-1] self.max_heapify(0) return largest def max_heapify(self, i): l = self.left_child(i) r = self.right_child(i) if (l <= self.Length() - 1 and self.Get_Index(l) > self.Get_Index(i)): largest = l else: largest = i if (r <= self.Length() - 1 and self.Get_Index(r) > self.Get_Index(largest)): largest = r if (largest != i): self.swap(largest, i) self.max_heapify(largest) def swap(self, i, j): self.heap[i], self.heap[j] = self.heap[j], self.heap[i] def Insert_data(self, key): index = self.Length() self.heap.append(key) while (index != 0): p = self.Parent(index) if self.Get_Index(p) < self.Get_Index(index): self.swap(p, index) index = p heap = BinaryHeap() print('Insert Element') print('max get') print('max extract') print('quit') while True: option = input('Enter the choice').split() choice = option[0].strip().lower() if choice == 'Insert Element': data = int(option[1]) heap.Insert_data(data) elif choice == 'max': suboperation = option[1].strip().lower() if suboperation == 'get': print('Maximum value: {}'.format(heap.get_max())) elif suboperation == 'extract': print('Maximum value removed: {}'.format(heap.Extract_maximum())) elif choice == 'quit': break
Let me explain the code to you. First, a class is created with several member functions inside it. We will see them one by one.
- The first method we used is Length. The Length() returns the number of elements in the heap.
- The second method is the left_child() which returns the index of the left child of the argument.
- The third method right_child() which returns the index of the right child of the argument.
- The next method Parent() returns the index of the parent of the argument.
- The Get_Index() method takes an index as an argument and returns the key at the index.
- The get_max() method gives the maximum element in the heap.
- The Extract_maximum() method removes the maximum element from the heap.
- The method max_heapify() modifies the heap structure to satisfy the heap property.
- The swap() method takes two indexes as arguments and exchanges the corresponding elements in the heap.
- The method Insert_data() takes a data element and adds that to the heap,
Output:
Insert Element max get max extract quit Enter the choice Insert Element 5 Enter the choice Insert Element 21 Enter the choice Insert Element 9 Enter the choice max extract Maximum value removed: 21 Enter the choice max get Maximum value : 9 Enter the choice max extract Maximum value removed: 9 Enter the choice Insert Element 45 Enter the choice max get Maximum value : 45 Enter the choice quit
Also read: Binary Tree in Python
Leave a Reply