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:
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:
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.