Data Structures for Coding Interviews in Python/

...

/

Max Heap (Implementation)

Max Heap (Implementation)

Let's implement a max Heap!

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).

Press + to interact
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.

Press + to interact
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) ...

Access this course and 1400+ top-rated courses and projects.