After swapping our largest value with the last value, our list now looks like this:
[None, 23, 22, 61, 10, 21, 13]
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.
MaxHeap. Its only parameter is
Inside the method, print
Declare a variable
idx and set it to
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
We’ll finish writing
.heapify_down() in the next method.