DEV Community

loading...

Max Heap in Python

lokesh05 profile image lokesh 惻Updated on 惻3 min read

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

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())) 
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide