Implementation of Min Heap in Python

Last Updated on June 29, 2022 by Ria Pathak

What is Heap?

Heap Data structure primarily focuses on representing priority queue.

Min – Heap follows the property of a complete binary tree in which the value of the internal node is smaller than or equal to the value of the children of that node.
In 0 – based indexing, the node stored at k index in the array will have its left child held at index 2k + 1 and its right child at index 2k + 2.

Representation of Min Heap:

Min heap is represented as an array. Below points shows indexes of other nodes for the ith node, i.e. Arr[i]:

• Arr[(i – 1) / 2] will return its parent node.
• Arr[(2 * i) + 1] will be its left child node.
• Arr[(2 * i) + 2] will be its right child node.

For Example 1: Using the above rules of array representation we can represent a heap in the array:

For node with value 2, its index value is 1 have left child is at (21) + 1 = 3 i.e. node with value 3 and right child is at (21) + 2 = 4 i.e. node with value 7. And we can see here that, both the children are bigger than their parent node.

For Example 2: Using the above rules of array representation we can represent a heap in the array:

For node with value 4, its index value is 2 have left child is at (22) + 1 = 5 i.e. node with value 16 and right child is at (22) + 2 = 6 i.e. node with value 18. And we can see here that, both the children are bigger than their parent node. Also its parent node will be at (2-1)/2 = 0 i.e. node with value 2.

Operations on Min Heap:

getMinimum(): This function will return the root element of the max heap. O(1) will be its time complexity.

extractMinimum(): This function will remove the minimum element from the Minheap. To maintain the heap property i.e. (calling heapify function) after removing the root, this function is having 0(Log n) time complexity.

insertNode(): For inserting the new key, 0(Log n) time is required. Using this function, we will add a new key at the end of the binary tree. If the new key is greater than its parent, then we have to fix the heap property which is violated here.

Note: We have to do indexing to simplify the below implementation.

Code Implementation

import sys

class MinHeap:

	def __init__(self, maxsize):
		self.maxsize = maxsize
		self.size = 0
		self.Heap = [0]*(self.maxsize + 1)
		self.Heap[0] = -1 * sys.maxsize
		self.FRONT = 1


	def parent(self, pos):
		return pos//2


	def leftChild(self, pos):
		return 2 * pos

	def rightChild(self, pos):
		return (2 * pos) + 1

	def isLeaf(self, pos):
		return pos*2 > self.size

	def swap(self, fpos, spos):
		self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]

	def minHeapify(self, pos):

		if not self.isLeaf(pos):
			if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or
			self.Heap[pos] > self.Heap[self.rightChild(pos)]):

				if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:
					self.swap(pos, self.leftChild(pos))
					self.minHeapify(self.leftChild(pos))

				else:
					self.swap(pos, self.rightChild(pos))
					self.minHeapify(self.rightChild(pos))

	def insert(self, element):
		if self.size >= self.maxsize :
			return
		self.size+= 1
		self.Heap[self.size] = element

		current = self.size

		while self.Heap[current] < self.Heap[self.parent(current)]:
			self.swap(current, self.parent(current))
			current = self.parent(current)

	def Print(self):
		for i in range(1, (self.size//2)+1):
			print(" PARENT : "+ str(self.Heap[i])+" LEFT CHILD : "+
								str(self.Heap[2 * i])+" RIGHT CHILD : "+
								str(self.Heap[2 * i + 1]))

	def minHeap(self):

		for pos in range(self.size//2, 0, -1):
			self.minHeapify(pos)

	def remove(self):

		popped = self.Heap[self.FRONT]
		self.Heap[self.FRONT] = self.Heap[self.size]
		self.size-= 1
		self.minHeapify(self.FRONT)
		return popped

if __name__ == "__main__":
	
	print('The minHeap is ')
	minHeap = MinHeap(15)
	minHeap.insert(10)
	minHeap.insert(35)
	minHeap.insert(19)
	minHeap.insert(7)
	minHeap.insert(21)
	minHeap.insert(15)
	minHeap.insert(6)
	minHeap.insert(22)
	minHeap.insert(9)
	minHeap.minHeap()

	minHeap.Print()
	print("The Min val is " + str(minHeap.remove()))

Output:
The minHeap is
PARENT : 6 LEFT CHILD : 9 RIGHT CHILD : 7
PARENT : 9 LEFT CHILD : 10 RIGHT CHILD : 21
PARENT : 7 LEFT CHILD : 19 RIGHT CHILD : 15
PARENT : 10 LEFT CHILD : 35 RIGHT CHILD : 22

The Min val is 6

Implementation Using Library Functions:

Heapq class will be used for implementing the built-in Min Heap in Python. And in this class, by default Min Heap is implemented.

Code Implementation

from heapq import heapify, heappush, heappop

heap = []
heapify(heap)

heappush(heap, 10)
heappush(heap, 35)
heappush(heap, 19)
heappush(heap, 7)
heappush(heap, 21)
heappush(heap, 15)
heappush(heap, 6)
heappush(heap, 22)
heappush(heap, 9)


print("Head value of heap : "+str(heap[0]))

print("The heap elements : ")
for i in heap:
	print(i, end = ' ')
print("\n")

element = heappop(heap)

print("The heap elements : ")
for i in heap:
	print(i, end = ' ')

Output:
Head value of heap : 6
The heap elements :
6 9 7 10 21 19 15 35 22

The heap elements :
7 9 15 10 21 19 22 35

This article tried to discuss the Implementation of Min Heap in Python. Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps.