After swapping our largest value with the last value, our list now looks like this:
Our heap is currently in violation of the rule that a parent should always be larger than its children. There’s no reason to get discouraged, we’ve handled this type of problem before, and we can get our MaxHeap 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. Inside the method, we will continuously swap values until our heap is restored.
Instructions
Define .heapify_down() in MaxHeap. Its only parameter is self.
Inside the method, print "Heapifying down!".
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 maximum.
Go back into .retrieve_max() and fix the method by calling .heapify_down() before we return max.
We’ll finish writing .heapify_down() in the next method.