- This chapter uses Max Heap, but the same concept could be applied on Min Heap as well by simple tweaking of logic.
At the very outset, even before going into more details, I want to make it clear that Heapify does not mean building a heap from a RANDOM array. Heapify operation can be done on a segment of an array arr[i...(n - 1)] if and only if elements in array segment arr[(i + 1)...(n - 1)] maintains heap property already, which means for a max heap:
arr[j] > arr[2 * j + 1] and arr[j] > arr[2 * j + 2]for an index j where j > i and j < n. After the heapify operation completes on arr[i...(n - 1)], arr[i] would contain the element which has the max value among all the elements in arr[i...(n - 1)] and arr[i...(n - 1)] would be a complete representation of a max heap. Now just by giving it a little thought, you would be able to figure that: given a random array you could build a heap out of it just by executing the Heapify operation on arr[n - 1], followed by arr[n - 2] and so on all the to arr. n = total number of elements in arr.
Now a very important observation: to call Heapify on an array segment, all the elements in the segment except the first one MUST maintain heap property. Now notice that the leaf nodes already exhibit heap property, since a leaf on its own is like an one node tree and an one node tree is a heap. So all the leaf nodes already maintain heap property.let'sthe last non-leaf node :
Index of Last non-leaf node = parent of last-node. = parent of node at (n-1)th index. = Node at index ((n-1) - 1)/2. = (n/2) - 1.
So, if total number of nodes = n, then number of leaf nodes = ceiling(n / 2), and number of non-leaf nodes = floor(n / 2). You could also deduce this relation just by reminding yourself the fact that heaps are COMPLETE BINARY TREES.So, we need to call heapify on elements from arr[n / 2] to arr.
Enough of theory. Let's look at the code below to have clear understanding of
This is a Premium content.
Please subscribe to Algorithms course to access the code.
MAX_HEAPIFY: O(height of the heap) = O(log2N), where N = total number of elements in the heap.
BUILD_MAX_HEAP: O(Nlog2N) since MAX_HEAPIFY is called O(N) times.
Senior SDE | Chief Architect
Microsoft | University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.