We’ve got a handy helper to tell us which child element is smaller, so there’s nothing standing between us and a pristine heap.
As a reminder, our strategy will be very similar to
.heapify_up(), but we’ll be moving down the tree. Here’s the general shape of the method:
# starting with our first element... # while there's at least one child present: # get the smallest child's index # compare the smallest child with our element # if our element is larger, swap with child # regardless, set our element index to be the child
We’ve added another helper method for you:
.child_present(). This returns a boolean indicating whether a given index has an associated child element. Use it wisely…
.heapify_down(), open up a while loop after your
The loop should run as long as
idx has a child element. Use the new helper method:
Print “Heapifying down!” within the loop.
Inside the loop, declare the variable
smaller_child_idx and set it equal to the appropriate value.
Declare two variables:
parent, set to the appropriate element from the internal list using
parent is greater than
child. If it is, we’ll need to make a swap.
Finish the loop by setting
idx equal to
smaller_child_idx. This is how we’ll terminate the loop, by moving down through the “tree” until there are no “child” elements to consider.
Outside the loop, print “Heap Restored!
Tab over to script.py and test it out.