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.
In the last exercise, we were pretty lucky that we only needed to make one swap in order to rebalance our heap. This isn’t always the case though, so we need to make sure our .heapify_down() method checks for all the possibilities.
As a reminder, our strategy for implementing .heapify_down() 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
set our element index to be the childWe’ve added another helper method: .child_present(). This returns a boolean indicating whether a given index has an associated child element.
Instructions
Inside of .heapify_down(), open up a while loop after the idx declaration.
The loop should run as long as idx has a child element. You will need to use the new helper method: .child_present().
Print "Heapifying down!" within the loop.
Inside the loop, declare the variable larger_child_idx and set it equal to the appropriate value.
Also inside the while loop, declare two variables: child and parent. We’ll use these variables to store the value of elements in heap_list at specific indexes.
Set each variable to the appropriate element value using the index values larger_child_idx and idx.
Create an if statement that checks if the value of parent is smaller than child.
If parent is smaller than child, we’ll need to make a swap. Inside the if statement, do the following:
- Set the value of
self.heap_list[idx]tochild. - Set the value of
self.heap_list[larger_child_idx]toparent.
Outside the if statement, finish the loop by setting idx equal to larger_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! {0}".format(self.heap_list)
Tab over to script.py and test it out.