Learn

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.

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?