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 takeO(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))
Top comments (0)