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.
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()))
Top comments (0)