Heapify Algorithm
Heapify is the process of converting an arbitrary array into a heap in O(n) time. It works by applying the down-heap operation on non-leaf nodes from the bottom up.
For a max-heap, heapify ensures every parent is larger than its children. The algorithm processes nodes from the last non-leaf node up to the root.
Max-Heapify (recursive or iterative)
public static void maxHeapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
swap(arr, i, largest);
maxHeapify(arr, n, largest);
}
}
Build Heap (heapify whole array)
public static void buildHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(arr, n, i);
}
}
Complexity analysis: Although heapify appears O(n log n), it is actually O(n) due to the distribution of work.
Two Minute Drill
- Heapify converts an array into a heap in O(n).
- Process non-leaf nodes from bottom up.
- Each node is bubbled down using maxHeapify/minHeapify.
- Used as the first step in heap sort.
Need more clarification?
Drop us an email at career@quipoinfotech.com