Building Efficiently

If you insert elements one by one into a heap, it takes O(N log N). Can we do better? Yes. O(N).

1. The Mathematical Anchor: Why O(N)?

This is a favorite interview “Staff Level” question. If sifting down takes O(log N), and we do it N/2 times, why isn’t it O(N log N)?

The “Bottom-Up” Realization

In a heap, the number of nodes at each height h is proportional to N / 2^h+1.

Most nodes (the leaves) are at height 0. They do 0 work.
Fewer nodes are at height 1. They do 1 step of work.
Only 1 node (the root) is at height log N. It does log N work.

The Summation

Total Work W = Σ_h=0^{log N} N/2^h+1 &cdot; h = N/2 Σ h &cdot; (1/2)^h. This is a convergent geometric series. The sum Σ_h=0^∞ h/2^h goes to 2.

Total Cost: N/2 &cdot; 2 = N.
Conclusion: Building a heap is linear!

2. Heapify Algorithm

Start from the last non-leaf node and siftDown backwards to the root. Mathematically, most nodes are at the bottom (leaves), and they travel 0 distance. Only the root travels log N. The sum converges to O(N).

Result

Sorted Array in O(N log N) space O(1).

3. Interactive: Sift Down

Visualize fixing a violated heap property. Node 50 is larger than children 10 and 20 in a Min Heap.

Root (50) is larger than children. Swap with smallest child.

4. Implementation

// Sift Down (Max Heap)
void heapify(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);
    heapify(arr, n, largest); // Recursively fix the affected subtree
  }
}