Learn

Great work so far! Our MaxHeap adds elements to heap_list, keeps count of the number elements inside the heap, and has the beginnings of .heapify_up().

Before we dive into the logic for .heapify_up(), let’s review how heaps track elements. We use a list for storing internal elements, but we’re modeling it on a binary tree, where every “parent” element has up to two “child” elements.

“child” and “parent” elements are determined by their relative indices within the internal list. By doing some arithmetic on an element’s index, we can determine the indices for parent and child elements (if they exist).

  • Parent: index // 2
  • Left Child: index * 2
  • Right Child: (index * 2) + 1
print(heap.heap_list) # Outputs: [None, 99, 22, 61, 10, 21, 13, 23] # Indices: [0, 1, 2, 3, 4, 5, 6, 7] heap.parent_idx(4) # (4 // 2) == 2 # Element at index 4 is 10 # Element at index 2 is 22 # The parent element of 10 is 22 heap.left_child(3) # (3 * 2) == 6 # Element at index 3 is 61 # Element at index 6 is 13 # The left child element of 61 is 13

These calculations are important for the efficiency of the heap, but they’re not necessary to memorize, so we’ve added three helper methods: .parent_idx(), .left_child_idx(), and .right_child_idx().

These helpers take an index as the argument and return the corresponding parent or child index.

Instructions

1.

Fill in the code in script.py to test out these new helper methods.

Sign up to start coding

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

Or sign up using:

Already have an account?