## DEV Community Tahir Raza

Posted on • Updated on

# 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