We mentioned .heapify_down()
is a lot like .heapify_up()
: we track an offending element in the heap and keep swapping it with another element until we’ve restored the heap properties.
In .heapify_up()
, we were always comparing our element with its parent. In .heapify_down()
, we have two possible elements to swap our root value with: the left child or the right child.
Once again, here is our current heap:
[None, 23, 22, 61, 10, 21, 13]
In order to restore our heap, we need to select the child with the larger value so that we can place it as the root of the heap. In our example, the two children of 23
are 22
and 61
. Since 61
is the larger child, we’ll swap it with 23
. After swapping the values, our list looks like this:
[None, 61, 22, 23, 10, 21, 13]
Our heap has been restored!
To accomplish this task, we’ll create another method in our MaxHeap
class called .get_larger_child_idx()
. Its purpose will be to return the index of the child with the larger value.
Instructions
Define .get_larger_child_idx()
, it will take self
and idx
as arguments.
We need to check if the element at the current index contains a right child. Use an if
statement to check if self.right_child_idx(idx)
is greater than self.count
.
If the condition returns True
, there is no right child. Inside the if
statement, do the following:
- print
"There is only a left child"
. - return the index of the left child.
If we do have a right child, we need to make a comparison to see if the left child or right child is larger.
Inside of an else
statement, declare left_child
and right_child
as variables and assign them to the appropriate elements from the internal list.
You can do this by using helper methods .left_child_idx()
and .right_child_idx()
to access elements in self.heap_list
.
Inside the else
statement from the previous checkpoint, make another conditional for the comparison between left_child
and right_child
.
If the left child is larger, print a message saying so and return the index of the left child.
Else, print a message saying the right child is larger and return the index of the right child.