Learn
Heaps: Python
Heapify Down I
We’ve retrieved the minimum element but left our MinHeap in disarray. There’s no reason to get discouraged, we’ve handled this type of problem before, and we can get our MinHeap back in shape!
We’ll define a method, .heapify_down(), which performs a similar role to .heapify_up(), except now we’re moving down the “tree” instead of up.
Instructions
1.
Define .heapify_down() on MinHeap, its only parameter is self.
Print “Heapifying down!”.
2.
Declare a variable idx and set it to 1.
Initially, this is pointing to our out-of-place value we swapped in while removing the minimum.
3.
Go back into .retrieve_min() and fix the method by calling .heapify_down() before we return min.