Generic selectors
Exact matches only
Search in title
Search in content
wb_sunny

Min Heap Data Structure – Complete Implementation in Python

Min Heap Implementation In Python

In this article, we will learn more about Min Heap (known as heap queue in Python). We have already learned about Heap and its library functions (in heapq module) in python. We will now learn about min-heap and its implementation and then look at the Python code for implementing the heapify, heappush and heappop functions ourselves. Let’s do a quick recap.

What is a Min heap?

A Min Heap is a complete binary tree (A complete binary tree is a tree that is completely filled, except for the rightmost nodes in the deepest/last level ) in which each node is smaller than or equal to all its children. Hence the root node of a heap is the smallest element. The min-heap data structure is generally used to represent a priority queue.

Min Heap Python AskPython Content1
Min Heap Example

How are heaps represented in arrays?

We have already seen how a heap is represented in memory in the form of an array, just a quick reminder that:

  • The root element will be at the zeroth position of the array, that is, Heap[0]. 
  • For any other node, say Heap[i], we have the following:
    • The parent node is given by : Heap[(i -1) / 2] 
    • The left child node is given by : Heap[(2 * i) + 1] 
    • The right child node is given by : Heap[(2 * i) + 2]
Min Heap Python AskPython Content21
Min Heap Python

Understanding the functions used in the implementation of Min Heap

1. min-heapify function

This function makes a node and all its descendants (child nodes and their child) follow the heap property. It rearranges the nodes by swapping them so as to make the given heap the smallest node in its subtree, following the heap property.

This function first finds the node with the smallest value amongst the given node and its children. It then swaps the given node, (say i) with the found minimum value node (say j), and then calls the min-heapify function (recursively) over node j, so as to make sure the new value assigned to node j does not break the heap property in its subtree.

Since at most, it has to traverse through the depth of the tree, its time complexity is O(d),where d is the depth, or, in terms of number of nodes, O(log n), n is the number of elements in the heap.

2. build-heap function

This function builds a heap from an arbitrary list (or any other iterable), that is, it takes the list and rearranges each element so as to satisfy the heap property. It can simply be implemented by applying min-heapify to each node repeatedly. The time complexity of this function comes out to be O(n) where n is the number of elements in heap.

3. heappop function

This function pops out the minimum value (root element) of the heap.

This is actually done by swapping the root node with the last node and deleting the now last node (containing minimum value) and then calling min-heapify for the root node so as to maintain the heap property after changes due to swapping.

Since we only need to deal with the descendants, the time complexity is O(log n), where n is the number of elements, or O(h), where h is the height of the tree which is log n as it is a complete tree.

4. heappush function

This function pushes a new element into the heap, and arranges it into its correct position, maintaining the heap property.

This is actually done by adding a new node to the end of the heap. Now to maintain the heap property, we traverse up from the last node (and swap where needed) to fix the heap property which could have been violated.

In a similar way as heappop, the time complexity here is O(log n) as we only need to traverse the height of the subtree.

5. extractMin function

This function returns the most priority (the root element) from the heap. Since we just need to return the value of the root and do no change to the heap, and the root is accessible in O(1) time, hence the time complexity of the function is O(1).

Complete Python Implementation of the Min Heap Data Structure

Following is the complete program for implementing min heap in python.

import sys

#defining a class min_heap for the heap data structure

class min_heap: 
    def __init__(self, sizelimit):
        self.sizelimit = sizelimit
        self.cur_size = 0
        self.Heap = [0]*(self.sizelimit + 1)
        self.Heap[0] = sys.maxsize * -1
        self.root = 1


    # helper function to swap the two given nodes of the heap
    # this function will be needed for heapify and insertion to swap nodes not in order
    def swapnodes(self, node1, node2):
        self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
 
    # THE MIN_HEAPIFY FUNCTION
    def min_heapify(self, i):
 
        # If the node is a not a leaf node and is greater than any of its child
        if not (i >= (self.cur_size//2) and i <= self.cur_size):
            if (self.Heap[i] > self.Heap[2 * i]  or  self.Heap[i] > self.Heap[(2 * i) + 1]): 
                if self.Heap[2 * i] < self.Heap[(2 * i) + 1]:
     # Swap the node with the left child and then call the min_heapify function on it
                    self.swapnodes(i, 2 * i)
                    self.min_heapify(2 * i)
 
                else:
                # Swap the node with right child and then call the min_heapify function on it
                    self.swapnodes(i, (2 * i) + 1)
                    self.min_heapify((2 * i) + 1)
 


    # THE HEAPPUSH FUNCTION
    def heappush(self, element):
        if self.cur_size >= self.sizelimit :
            return
        self.cur_size+= 1
        self.Heap[self.cur_size] = element 
        current = self.cur_size
        while self.Heap[current] < self.Heap[current//2]:
            self.swapnodes(current, current//2)
            current = current//2
 
 
    # THE HEAPPOP FUNCTION
    def heappop(self):
        last = self.Heap[self.root]
        self.Heap[self.root] = self.Heap[self.cur_size]
        self.cur_size -= 1
        self.min_heapify(self.root)
        return last
 
 
    # THE BUILD_HEAP FUNCTION
    def build_heap(self): 
        for i in range(self.cur_size//2, 0, -1):
            self.min_heapify(i)
 
 
    # helper function to print the heap
    def print_heap(self):
        for i in range(1, (self.cur_size//2)+1):
            print("Parent Node is "+ str(self.Heap[i])+" Left Child is "+ str(self.Heap[2 * i]) +                  " Right Child is "+ str(self.Heap[2 * i + 1]))
 
 
# Driver Code
minHeap = min_heap(10)
minHeap.heappush(15)
minHeap.heappush(7)
minHeap.heappush(9)
minHeap.heappush(4)
minHeap.heappush(13)
minHeap.print_heap()

Output:

Parent Node is 4 Left Child is 7 Right Child is 9
Parent Node is 7 Left Child is 15 Right Child is 13

Coclusion

In this article, We learned about min heap. We studied how the functions for heapify, heappush and heappop work. We further implemented the min heap data structure from scratch in python from scratch. Stay tuned for more informative articles.

Happy Learning!