If you don't know - Heap is one of the awesome data structures you should learn. Why?
- Heap can find min/max in
- Insertion/Deletion can be done in
O(logn)whereas in arrays insertion take
- 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))