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.
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]
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!