Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Python

Max Heap (Implementation)

Explore the implementation of a max heap in Python. Learn how to insert elements, retrieve the maximum, remove the maximum, and build a heap from a list. Understand the underlying heap property restoration methods with detailed time complexity analysis.

We'll cover the following...

Max-heap Implementation

Let’s start with some function declarations for the heap class. The __percolateUp() function is meant to restore the heap property going up from a node to the root. The __maxHeapify() function restores the heap property starting from a given node down to the leaves. The two underscores before the __percolateUp() and __maxHeapify() functions imply that these functions should be treated as private functions although there is no actual way to enforce class function privacy in Python. You can still call these functions by prepending _className like so, heap._maxHeap__percolateUp(index).

Python 3.5
class MaxHeap:
    def __init__(self):
        pass
    def insert(self, val):
        pass
    def getMax(self):
        pass
    def removeMax(self):
        pass
    def __percolateUp(self, index):
        pass
    def __maxHeapify(self, index):
        pass
heap = MaxHeap()

Implementing the constructor

The constructor will initialize a list that will contain the values of the heap.

Python 3.5
class MaxHeap:
    def __init__(self):
        self.heap = []
    def insert(self, val):
        pass
    def getMax(self):
        pass
    def removeMax(self):
        pass
    def __percolateUp(self, index):
        pass
    def __maxHeapify(self, index):
        pass
heap = MaxHeap()

Implementing the insert() function

This function appends the given value to the heap list and calls the __percolateUp() function on it. This function will swap the values at parent-child nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) ...