Heapify a list into Max Heap

If you don't know - Heap is one of the awesome data structures you should learn. Why?

Heap can find min/max in O(1)
Insertion/Deletion can be done in O(logn) whereas in arrays insertion take O(n)
If you learn this data structure, you will be able to grasp heap-sort, priority queue and heapifying an array concept.

If you are interested to learn more about Heaps, here are some resources to get you started:

So how you can convert an array to a Heap.

list = [20, 5, 30, 10, 15, 45]

def getChildren(pIndex, list):
    leftIndex = pIndex * 2 + 1
    rightIndex = pIndex * 2 + 2

    left = -1
    if leftIndex < len(list):
        left = list[leftIndex]

    right = -1
    if rightIndex < len(list):
        right = list[rightIndex]

    return left, right

def heapify(list):

    for i in range(len(list)-1, -1, -1):
        p = list[i]
        left, right = getChildren(i, list)

        bigChild = max(left, right)

        bigChildIndex = 2 * i + 1
        if right == max(left, right):
            bigChildIndex = 2 * i + 2

        j = i
        while p < bigChild and bigChildIndex < len(list) and j < len(list):
            list[j] = bigChild
            list[bigChildIndex] = p

            j = bigChildIndex
            left, right = getChildren(j, list)
            bigChild = max(left, right)
            bigChildIndex = 2 * j + 1

    return list

print(heapify(list))

Photo by Pixabay

Blog

Heapify a list into Max Heap

Tahir Raza

Join Our Newsletter. No Spam, Only the good stuff.

Related