.heapify_down() is a lot like
.heapify_up(). We’ll track an offending element in the heap, and keep swapping it with another element until we’ve restored the heap properties.
The wrinkle is
.heapify_down() gives us another option for which element to swap. In
.heapify_up(), we were always comparing our element with its parent. In
.heapify_down(), we have potentially two options: the left child and the right child.
Which should we choose? We’ll use an example to think it through. Imagine we have a heap with four elements:
print(heap.heap_list) # [None, 21, 36, 58, 42] heap.retrieve_min() # 21 # [None, 42, 36, 58] # Should we swap with 36 or 58?
We want to swap with the smaller of the two children, otherwise, we wouldn’t maintain our heap properties!
Let’s write a helper method to determine the smallest child element for a given index. We’ll make heavy use of our other helper methods:
.get_smaller_child_idx() will have the following structure:
# check if we have a right child # if we don't, return the left child index # if we do... # return the index of the smaller child
.get_smaller_child_idx(), it will take
idx as arguments.
Check if we have a right child for this index. We don’t if the right child index is greater than our internal count.
If we don’t, print “There is only a left child” and return the left child index.
If we do have a right child, we need to make a comparison to see which is smaller.
right_child as variables and assign them to the appropriate elements from the internal list.
You can do this by using helper methods
.right_child_idx() to access elements in
Make another conditional for the comparison between
If the left child is smaller, print a message saying so and return the index of the left child.
Else, do the same but for the right child.
Tab over to script.py and test out this new method by replacing
None with the correct index value.