Implementation of Max Heap in Python

Max-Heap

Max-Heap follows the property of a complete binary tree in which the value of the internal node is greater than or equal to the value of the children of that node.
A 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 Max Heap:

Max 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] returns its parent node.
  • Arr[(2 * i) + 1] returns its left child node.
  • Arr[(2 * i) + 2] returns its right child node.

For Example 1:

For node with value 6, 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 2. 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 14, its index value is 2 have left child is at (22) + 1 = 5 i.e. node with value 6 and right child is at (22) + 2 = 6 i.e. node with value 8. And we can see here that, both the children are smaller than their parent node. Also its parent node will be at (2-1)/2 = 0 i.e. node with value 18.

Operations on Max Heap:

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

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

  3. 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 smaller 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 MaxHeap:

	def __init__(self, maxsize):
		
		self.maxsize = maxsize
		self.size = 0
		self.Heap = [0] * (self.maxsize + 1)
		self.Heap[0] = 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):
		
		if pos >= (self.size//2) and pos <= self.size:
			return True
		return False

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

	def maxHeapify(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.maxHeapify(self.leftChild(pos))

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

	def insertNode(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 NODE : " + str(self.Heap[i]) +
				" LEFT CHILD : " + str(self.Heap[2 * i]) +
				" RIGHT CHILD : " + str(self.Heap[2 * i + 1]))

	def extractMaximum(self):

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

if __name__ == "__main__":
	
	maxHeap = MaxHeap(15)
	maxHeap.insertNode(5)
	maxHeap.insertNode(9)
	maxHeap.insertNode(1)
	maxHeap.insertNode(11)
	maxHeap.insertNode(28)
	maxHeap.insertNode(19)
	maxHeap.insertNode(7)
	maxHeap.insertNode(2)
	maxHeap.insertNode(8)

	maxHeap.Print()
	
	print("The Max val is of Max Heap will be " + str(maxHeap.extractMaximum()))

Output:
PARENT NODE : 28 LEFT CHILD : 11 RIGHT CHILD : 19
PARENT NODE : 11 LEFT CHILD : 8 RIGHT CHILD : 9
PARENT NODE : 19 LEFT CHILD : 1 RIGHT CHILD : 7
PARENT NODE : 8 LEFT CHILD : 2 RIGHT CHILD : 5
The Max val is of Max Heap will be 28

Implementation Using Library Functions:

Heapq class will be used for implementing the built-in Max Heap in Python. And in this class, by default Min Heap is implemented. For Implementing Max Heap, we have to multiply all the keys with -1.

Code Implementation


from heapq import heappop, heappush, heapify

heap = []
heapify(heap)

heappush(heap, -1 * 5)
heappush(heap, -1 * 9)
heappush(heap, -1 * 1)
heappush(heap, -1 * 11)
heappush(heap, -1 * 28)
heappush(heap, -1 * 19)
heappush(heap, -1 * 7)
heappush(heap, -1 * 2)
heappush(heap, -1 * 8)

print("The Head value of heap is : "+str(-1 * heap[0]))

print("Heap elements are : ")
for i in heap:
	print(-1 * i, end = ' ')
print("\n")

element = heappop(heap)

Output:
The Head value of heap is : 28
Heap elements are :
28 11 19 8 9 1 7 2 5

The heap elements :
19 11 7 8 9 1 5 2

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

Leave a Reply

Your email address will not be published. Required fields are marked *