Binary heap implementation in Python

By Sachin Verma

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.

1.  The first method we used is Length. The Length()  returns the number of elements in the heap.
2.  The second method is the left_child() which returns the index of the left child of the argument.
3.  The third method right_child() which returns the index of the right child of the argument.
4. The next method Parent() returns the index of the parent of the argument.
5. The Get_Index() method takes an index as an argument and returns the key at the index.
6. The get_max() method gives the maximum element in the heap.
7. The Extract_maximum() method removes the maximum element from the heap.
8. The method max_heapify() modifies the heap structure to satisfy the heap property.
9. The swap() method takes two indexes as arguments and exchanges the corresponding elements in the heap.
10. 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