Skip to Content
Learn
Heaps: Python
Translating Parent and Child Elements Into Indices

Great work so far! Our MinHeap adds elements to the internal list, keeps a running count, 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) # [None, 10, 13, 21, 61, 22, 23, 99] # Indices: [0, 1, 2, 3, 4, 5, 6, 7] heap.parent_idx(4) # (4 // 2) == 2 # Element at index 4 is 61 # Element at index 2 is 13 # The parent element of 61 is 13 heap.left_child(3) # (3 * 2) == 6 # Element at index 3 is 21 # Element at index 6 is 23 # The left child element of 21 is 23

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.

Folder Icon

Sign up to start coding

Already have an account?