Max Heap in Python
Tags: python, heapsort, datastructures
Published: 2021-04-21 16:12:55

A Max-Heap is a complete binary tree that stores data so that every child node is less than or equal to each of its parent node. The root node will always store the largest value, while the leaf node will store the smallest values.

![alt text](https://cdn.journaldev.com/wp-content/uploads/2020/08/heap.png)



##Representation of Max-Heap:
A Max-heap is often represented as an array.
The indexes of nodes for Arr[i]:

1) The index starts from 0; hence, the root element will be at Arr[0].
2) The parent node of the child is at index Arr[(i-1)/2].   

*‘i’ is the index of the child.*

3) The children of a particular parent node
   Arr[(2i)+1] Returns the left child node.
   Arr[(2i)+2] Returns the right child node.

*Where i= index of a parent node.*


##Operations on Max-Heap:
**getMax():** It returns the maximum root value.

**extractMax():** It extracts and removes the maximum element.

**insert():** It inserts a new key at the end of the tree.

*If new key is bigger than its parent, we need to traverse up to fix the violated binary tree.*


##Code in Python:
```
# implementation of Max Heap 
import sys 
# create a class for Maximum Heap
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

	# Function to return the position of parent node
	def parent(self, pos): 	
		return pos // 2

	# return the position of left child
	def left_Child(self, pos): 	
		return 2 * pos 

	# return the position of right child	
	def right_Child(self, pos): 	
		return (2 * pos) + 1


	# node is a leaf node; returns true if the passed 
	def isLeaf(self, pos): 	
		if pos >= (self.size//2) and pos <= self.size: 
			return True
		return False

	# Function to swap two nodes of the heap 
	def swap(self, fpos, spos): 		
		self.Heap[fpos], self.Heap[spos] = (self.Heap[spos], 
											self.Heap[fpos]) 

	# Function to heapify the node at pos
    # heapify() converts the iterable into a heap data 
	def maxHeapify(self, pos): 

		# If the node is a non-leaf node and smaller 
		if not self.isLeaf(pos): 
			if (self.Heap[pos] < self.Heap[self.left_Child(pos)] or
				self.Heap[pos] < self.Heap[self.right_Child(pos)]): 

				# Swap with the left child and heapify 
				if (self.Heap[self.left_Child(pos)] > 
					self.Heap[self.right_Child(pos)]): 
					self.swap(pos, self.left_Child(pos)) 
					self.maxHeapify(self.left_Child(pos)) 

				# Swap with the right child and heapify 
				else: 
					self.swap(pos, self.right_Child(pos)) 
					self.maxHeapify(self.right_Child(pos)) 

	# insert a node into the heap 
	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) 

	# Function to print the contents of the heap 
	def Print(self): 
		
		for i in range(1, (self.size // 2) + 1): 
			print(" PARENT NODE : " + str(self.Heap[i]) +
				" LEFT CHILD NODE : " + str(self.Heap[2 * i]) +
				" RIGHT CHILD NODE : " + str(self.Heap[2 * i + 1])) 

	# Function to remove and return the maximum element
	def extractMax(self): 
# pop() removes and returns last value from the list
		popped = self.Heap[self.FRONT] 
		self.Heap[self.FRONT] = self.Heap[self.size] 
		self.size -= 1
		self.maxHeapify(self.FRONT) 
		
		return popped 

# Driver Code 
if __name__ == "__main__": 
	
	print('The MaxHeap = ') 
	
	maxHeap = MaxHeap(25) 
	maxHeap.insert(1) 
	maxHeap.insert(3) 
	maxHeap.insert(5)  
	maxHeap.insert(8) 

	maxHeap.Print() 
	
	print("The Maximum value is " + str(maxHeap.extractMax())) 
```