Skip to Content
Learn
Heaps: Python
Adding an Element: Heapify Up II

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 greater in value than their parent. Say we add an element to the following heap:

print(heap.heap_list) # [None, 10, 13, 21, 61, 22, 23, 99] heap.add(12) # ( new_element ) # { parent_element } # [None, 10, 13, 21, {61}, 22, 23, 99, (12)]

Oh no! We’ve violated the heap property: 12‘s parent is 61, the parent element is greater than the child.

Don’t fret; we can fix this. We’ll exchange the parent and the child elements.

# [None, 10, 13, 21, {61}, 22, 23, 99, (12)] # SWAP 12 and 61 # [None, 10, 13, 21, (12), 22, 23, 99, {61}]

12‘s parent is now 13, they’re close but the parent element is still greater than the child. Keep on swappin’!

# [None, 10, {13}, 21, (12), 22, 23, 99, 61] # SWAP 12 and 13 # [None, 10, (12), 21, {13}, 22, 23, 99, 61]

Okay, you can let out that sigh of relief. We’ve restored the heap properties!

# [None, {10}, (12), 21, 13, 22, 23, 99, 61] # The child, 12, is greater than the parent, 10!

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 greater: # swap the elements # set the target element index to be the parent's index

Instructions

1.

Inside of .heapify_up(), declare a variable called idx and set it to the last index of the internal list.

2.

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, set idx to be 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.

3.

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 greater than child.

If it is greater, print the message: “swapping parent_element with element_at_index“.

4.

If the parent element is larger than the element at idx, we need to swap to restore the heap properties.

Swap the elements by setting the value at idx to be parent and the value at self.parent_idx(idx) to be child!

5.

When the loop ends, congratulations, you’ve restored your heap.

Print the message “Heap Restored self.heap_list

Tab over to script.py and run the code to enjoy the fruits of your labor!

Folder Icon

Sign up to start coding

Already have an account?