Heapify
Get started
- 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[0]. 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[0].
Enough of theory. Let's look at the code below to have clear understanding of
MAX_HEAPIFY and BUILD_MAX_HEAP.
Login to Access Content
Time Complexity:
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.
