Now that we understand how to determine the relationship of elements with the internal list, we’re ready to finish .heapify_up()
.
We need to make sure that every child is smaller in value than their parent. Say we add an element to the following heap:
print(heap.heap_list) # Output: [None, 99, 22, 61, 10, 21, 13, 23] heap.add(90) # ( new_element ) # { parent_element } # [None, 99, 22, 61, {10}, 21, 13, 23, (90)]
Oh no! We’ve violated the heap property: since 90
‘s parent is 10
, the parent element is smaller than the child.
Don’t fret; we can fix this. We’ll exchange the parent and the child elements.
# [None, 99, 22, 61, {10}, 21, 13, 23, (90)] # SWAP 90 and 10 # [None, 99, 22, 61, (90), 21, 13, 23, {10}]
90
‘s parent is now 22
, so the parent element is still smaller than the child. Keep on swappin’!
# [None, 99, 22, 61, (90), 21, 13, 23, 10] # SWAP 22 and 90 # [None, 99, (90), 61, {22}, 21, 13, 23, 10]
Okay, you can let out that sigh of relief. We’ve restored the heap properties!
# [None, {99}, (90), 61, 22, 21, 13, 23, 10] # The parent, 99, is greater than the child, 90!
Let’s recap our strategy for .heapify_up()
:
start at the last element of the list
while there's a parent element available:
if the parent element is smaller:
swap the elements
set the target element index to be the parent's index
Instructions
Inside of .heapify_up()
, declare a variable called idx
and set it to the last index of the internal list.
Set up a while loop that will run as long as there is a valid parent index. A valid parent index is anything greater than 0
.
Inside the loop condition, set idx
as the index of its parent. This will be the last part of the loop, but we’re writing it first so we don’t get stuck in infinite loops.
At the beginning of the loop, declare a variable child
and set it equal to the element in the internal list at idx
.
Declare another variable parent
and set it equal to the element in the internal list at self.parent_idx(idx)
.
Check to see if parent
is smaller than child
.
If the parent value is smaller, print the message: “swapping parent_element
with element_at_index
“.
If the parent element is smaller than the element at idx
, we need to swap to restore the heap properties.
Inside the conditional statement, swap the elements by setting the value at idx
to be parent
and the value at self.parent_idx(idx)
to be child
!
When the loop ends, congratulations, you’ve restored your heap.
Print the value "HEAP RESTORED! {0}".format(self.heap_list)
outside th while
loop.
Tab over to script.py and run the code to enjoy the fruits of your labor.