Question
In the context of this lesson, where we implemented a min heap, how can we implement a max heap?
Answer
Implementing a max heap is very similar to how we implemented a min heap in the lesson.
For a max heap, instead of maintaining the heap property of a min heap such that every parent element is less than or equal to both children, we want to maintain that every parent element is greater than or equal to both children elements. To do this, you can update the methods so that the comparisons take into account this property instead. In addition, you might consider renaming the get_smaller_child_idx method for getting the greater child instead.
For instance, one such update would be in the heapify_up method, which we want to check if the parent is less than the child element, so that we use the < operator to compare them, like so
if self.heap_list[self.parent_idx(idx)] < self.heap_list[idx]
We would then would swap the parent and child element if the parent is less than the child, so that the larger elements are at the top of the max heap.