Algo: Heap -> Heapify

heapify.py

def heapify(array):
    last_index = len(array) - 1
    for index in range(last_index, -1, -1):
        bubble_down(array, index)    


def bubble_down(array, index):
    index_limit = len(array) - 1
    lchild_index = (index + 1) * 2 - 1
    rchild_index = lchild_index + 1
    
    left_child = array[lchild_index] if (lchild_index <= index_limit) else 0
    right_child = array[rchild_index] if (rchild_index <= index_limit) else 0

    if (array[index] < left_child or array[index] < right_child):
        max_child_index = lchild_index if left_child > right_child else rchild_index
        array[index], array[max_child_index] = array[max_child_index], array[index]
        bubble_down(array, max_child_index)


# Main
heapify([10, 20, 15, 12, 40, 25, 18])

# Before: 
# [10, 20, 15, 12, 40, 25, 18]
#
#       10
#   20      15
# 12  40  25  18

# After:
# [40, 20, 25, 12, 10, 15, 18]
#
#       40
#   20      25
# 12  10  15  18

Ref: Abdul Bari - Heapify