Building a Max Heap

When constructing a max heap from an array of N elements, the goal is to arrange the elemetns in a structure that satisfies the max heap property: every parent node must be greater than or equal to its child nodes.

There are two primary strategies:

1. Inserting elements one by one into an initially empty heap, wich results in a time complexity of O(N log N).
2. Constructing the heap in linear time O(N) by first arranging the elements in an array to form a complete binary tree, and then applying heapify operations from the last parent node up to the root.

This article focuses on the second, more efficient method for heap construction.

Linear Time Heap Construction

The steps are as follows:

1. Store all N elements in an array while preserving the complete binary tree structure.
2. Starting from the last parent node (i.e., index (N/2)-1), apply a sift-down or heapify-down operation to ensure the max heap property is satisfied for each subtree.

Example Walkthrough

Consider an array of elements initially arranged in arbitrary order. We begin heapifying from the last parent node and proceed backwards to the root:

• Start with the parent node at index 3. If it is smaller than its largest child, swap it with that child.
• Move to index 2 and repeat the process, comparing the node with its children and swapping if necessary.
• Continue this until the root node is processed, at which point the entire structure becomes a valid max heap.

Implementation Details

The following Java implementation demonstrates the heapify-down operation and the overall heap creation process:

public static void heapifyDown(HeapData heap, int startIdx) {
    Integer[] data = heap.getArray();
    Integer rootVal = data[startIdx];
    int parentIdx = startIdx;
    int heapSize = heap.getSize();

    while (parentIdx * 2 + 1 < heapSize) {
        int leftChildIdx = parentIdx * 2 + 1;
        int rightChildIdx = leftChildIdx + 1;
        int largerChildIdx = leftChildIdx;

        if (rightChildIdx < heapSize && data[leftChildIdx].compareTo(data[rightChildIdx]) < 0) {
            largerChildIdx = rightChildIdx;
        }

        if (rootVal.compareTo(data[largerChildIdx]) >= 0) {
            break;
        }

        data[parentIdx] = data[largerChildIdx];
        parentIdx = largerChildIdx;
    }

    data[parentIdx] = rootVal;
}

@Test
public void buildMaxHeap() {
    HeapData heap = HeapSetup.createHeap(20);
    for (int i = 0; i < 11; i++) {
        heap.getArray()[i] = i; // Initialize with sample values
    }

    for (int i = (heap.getSize() - 1) / 2; i >= 0; i--) {
        HeapOperations.heapifyDown(heap, i);
    }
}