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 child
We’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.