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))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
class MaxHeap:
    def __init__(self):
        self.heap = []
    def insert(self, val):
        self.heap.append(val)
        self.__percolateUp(len(self.heap)-1)
    def getMax(self):
        pass
    def removeMax(self):
        pass
    def __percolateUp(self, index):
        pass
    def __maxHeapify(self, index):
        pass
heap = MaxHeap()

Implementing the getMax() function

This function returns the maximum value in the heap which is the root, i.e., the first value in the list. It does not modify the heap itself. The time complexity of this function is in O(1)O(1) constant time which is what makes heaps so special!

Press + to interact
class MaxHeap:
    def __init__(self):
        self.heap = []
    def insert(self, val):
        self.heap.append(val)
        self.__percolateUp(len(self.heap)-1)
    def getMax(self):
        if self.heap:
            return self.heap[0]
        return None
    def removeMax(self):
        pass
    def __percolateUp(self, index):
        pass
    def __maxHeapify(self, index):
        pass
heap = MaxHeap()

Implementing the removeMax() function

This function removes and returns the maximum value in the heap. It first checks if the length of the heap is greater than 1, if it is, it saves the maximum value in a variable, swaps the maximum value with the last leaf, deletes the last leaf, and restores the max heap property on the rest of the tree by calling the __maxHeapify() function on it. The function then checks if the heap is of size 1, if it is, it saves the maximum value in the tree (the only value really) in a variable, deletes it, and returns it. Then it checks if the heap is empty and returns None if it is. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
class MaxHeap:
    def __init__(self):
        self.heap = []
    def insert(self, val):
        self.heap.append(val)
        self.__percolateUp(len(self.heap)-1)
    def getMax(self):
        if self.heap:
            return self.heap[0]
        return None
    def removeMax(self):
        if len(self.heap) > 1:
            max = self.heap[0]
            self.heap[0] = self.heap[-1]
            del self.heap[-1]
            self.__maxHeapify(0)
            return max
        elif len(self.heap) == 1:
            max = self.heap[0]
            del self.heap[0]
            return max
        else:
            return None
    def __percolateUp(self, index):
        pass
    def __maxHeapify(self, index):
        pass
heap = MaxHeap()

Implementing the __percolateUp() function

This function restores the heap property by swapping the value at a parent node if it is less than the value at a child node. After swapping, the function is called recursively on each parent node until the root is reached. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
class MaxHeap:
    def __init__(self):
        self.heap = []
    def insert(self, val):
        self.heap.append(val)
        self.__percolateUp(len(self.heap)-1)
    def getMax(self):
        if self.heap:
            return self.heap[0]
        return None
    def removeMax(self):
        if len(self.heap) > 1:
            max = self.heap[0]
            self.heap[0] = self.heap[-1]
            del self.heap[-1]
            self.__maxHeapify(0)
            return max
        elif len(self.heap) == 1:
            max = self.heap[0]
            del self.heap[0]
            return max
        else:
            return None
    def __percolateUp(self, index):
        parent = (index-1)//2
        if index <= 0:
            return
        elif self.heap[parent] < self.heap[index]:
            tmp = self.heap[parent]
            self.heap[parent] = self.heap[index]
            self.heap[index] = tmp
            self.__percolateUp(self, parent)
    def __maxHeapify(self, index):
        pass
heap = MaxHeap()

Implementing the __maxHeapify() function

This function restores the heap property after a node is removed. It swaps the values of the parent nodes with the values of their largest child nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
class MaxHeap:
    def __init__(self):
        self.heap = []
    def insert(self, val):
        self.heap.append(val)
        self.__percolateUp(len(self.heap)-1)
    def getMax(self):
        if self.heap:
            return self.heap[0]
        return None
    def removeMax(self):
        if len(self.heap) > 1:
            max = self.heap[0]
            self.heap[0] = self.heap[-1]
            del self.heap[-1]
            self.__maxHeapify(0)
            return max
        elif len(self.heap) == 1:
            max = self.heap[0]
            del self.heap[0]
            return max
        else:
            return None
    def __percolateUp(self, index):
        parent = (index-1)//2
        if index <= 0:
            return
        elif self.heap[parent] < self.heap[index]:
            tmp = self.heap[parent]
            self.heap[parent] = self.heap[index]
            self.heap[index] = tmp
            self.__percolateUp(parent)
    def __maxHeapify(self, index):
        left = (index * 2) + 1
        right = (index * 2) + 2
        largest = index
        if len(self.heap) > left and self.heap[largest] < self.heap[left]:
            largest = left
        if len(self.heap) > right and self.heap[largest] < self.heap[right]:
            largest = right
        if largest != index:
            tmp = self.heap[largest]
            self.heap[largest] = self.heap[index]
            self.heap[index] = tmp
            self.__maxHeapify(largest)

Implementing the buildHeap() function #

This function restores creates a heap from a list passed as an argument. It calls _maxHeapify method at every index starting from the last index of the list building a heap.

Press + to interact
class MaxHeap:
    def __init__(self):
        self.heap = []
    def insert(self, val):
        self.heap.append(val)
        self.__percolateUp(len(self.heap)-1)
    def getMax(self):
        if self.heap:
            return self.heap[0]
        return None
    def removeMax(self):
        if len(self.heap) > 1:
            max = self.heap[0]
            self.heap[0] = self.heap[-1]
            del self.heap[-1]
            self.__maxHeapify(0)
            return max
        elif len(self.heap) == 1:
            max = self.heap[0]
            del self.heap[0]
            return max
        else:
            return None
    def __percolateUp(self, index):
        parent = (index-1)//2
        if index <= 0:
            return
        elif self.heap[parent] < self.heap[index]:
            tmp = self.heap[parent]
            self.heap[parent] = self.heap[index]
            self.heap[index] = tmp
            self.__percolateUp(parent)
    def __maxHeapify(self, index):
        left = (index * 2) + 1
        right = (index * 2) + 2
        largest = index
        if len(self.heap) > left and self.heap[largest] < self.heap[left]:
            largest = left
        if len(self.heap) > right and self.heap[largest] < self.heap[right]:
            largest = right
        if largest != index:
            tmp = self.heap[largest]
            self.heap[largest] = self.heap[index]
            self.heap[index] = tmp
            self.__maxHeapify(largest)
    def buildHeap(self, arr):
        self.heap = arr
        for i in range(len(arr)-1, -1, -1):
            self.__maxHeapify(i)

Let’s derive a tight bound for the complexity of building a heap.

Notice that we start from the bottom of the heap, i.e., range(len(arr)-1,-1,-1) (line 54). The number of comparisons for a particular node at height ...