Can you please confirm the meaning of the concept 'heapify', the source I am learning from says that heapify is building a heap from an array (from scratch)
This is how I understand after googling several resources
Heapify is:
- after we popped the top node of the heap and we moved the last node to the top then we rearrange the tree from top-to-bottom so it is a heap again (we heapify)
- heapify time complexity O(log n)
Heapify is not:
- creating a heap from an array which is a bottom-up operation with a time complexity of O(n)
Is this right?
2 Answers
Basically, heapify is an algorithm used to re-arrange the heap if the root node violates the heap property (child subtrees must be heaps!). It's a vital part of building a heap, inserting or deleting a top node from the heap.
Heapify is:
- after we popped the top node of the heap and we moved the last node to the top then we rearrange the tree from top-to-bottom so it is a heap again (we heapify)
- heapify time complexity O(log n)
Here you describe how heapify is used if the top element is removed. Yep, it's a valid case because you need to keep your max/min element at the top (depending on whether it's a max heap or a min heap).
Heapify is not:
creating a heap from an array which is a bottom-up operation with a time complexity of O(n)
You're right, it's not. As said before, heapify is just a way to maintain heap properties after performing operations on it.
You use heapify for building a heap to make sure your resulting data structure meets heap requirements. For example, given you need to build a min heap from an array, you can do it as follows:
def min_heapify(arr, index): size = len(arr) new_index = index left = index * 2 + 1 right = index * 2 + 2 if (left < size and arr[left] < arr[new_index]): new_index = left if (right < size and arr[right] < arr[new_index]): new_index = right if (new_index != index): arr[index], arr[new_index] = arr[new_index], arr[index] min_heapify(arr, new_index) array = [5, 4, 3, 2, 1] size = len(array) for i in range((size//2) - 1, -1, -1): min_heapify(array, i) print (array) [1, 2, 3, 5, 4]
As you can see, even though heapify is actively used for building a heap, we cannot say that building a heap is heapify. It's just an essential part of the process.
Heapify is the process of converting a binary tree into a Heap data structure in O(N).
Heapify starts from leaf nodes and checks if each subtree is a heap or not. If not heap, check downward and make it adjust it to make a heap. we repeat these steps for all nodes until we reach the root
