CodeWithYash

Intermediate · Module 14 · Lesson 2

Heapify

Sift values up or down and build a heap in linear time.

15–25 min readLesson 78 of 123

Lesson 78 of 123

1d streak

Heapify: Why Building a Heap Takes O(n) Instead of O(n log n)

Building a heap from an unsorted array by successive insert() calls takes $O(n log n)$ time. In contrast, Floyd’s Bottom-Up Heapify algorithm converts an entire array of size $n$ into a valid heap in strictly O(n) linear time.

Why Bottom-Up Heapify is O(n): The Geometric Intuition
Successive Inserts (Top-Down):
- Leaves (n/2 nodes) are inserted LAST and can each sift up the full height h = log n.
- Work = (n/2) * log n = O(n log n)!

Bottom-Up Heapify:
- Sift-down begins at the first NON-LEAF node: index (n / 2) - 1 down to 0!
- The n/2 leaf nodes require 0 swaps (height 0).
- The n/4 nodes at height 1 can sift down at most 1 level.
- The n/8 nodes at height 2 can sift down at most 2 levels.
- Exactly 1 root node at height log n can sift down log n levels.

Total Work: Sum of (n / 2^(h+1)) * h = n * Sum(h / 2^h) ≈ n * 2 = O(n)!
HeapifyImplementation.java
public void buildHeap(int[] arr) {
    int n = arr.length;
    // Start from the last non-leaf node: (n / 2) - 1 down to 0
    for (int i = (n / 2) - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
}

private void siftDown(int[] arr, int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] < arr[smallest]) smallest = left;
    if (right < n && arr[right] < arr[smallest]) smallest = right;

    if (smallest != i) {
        int temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;
        siftDown(arr, n, smallest); // Continue sifting down
    }
}

Cost Model

Complexity & Trade-offs

Push / pop
O(log n)
O(n)
Reading the root is O(1); heap construction is O(n).

When to use it

  • Top-k, streaming medians, scheduling, and best-first frontiers.
  • Repeated access to an extreme without fully sorting.
  • Merging sorted sources.

Common mistakes

  • Choosing the wrong heap direction for a bounded top-k set.
  • Assuming heap iteration is globally sorted.
  • Claiming bottom-up heap construction is O(n log n).

Practice prompts

  • Reproduce the worked Heapify example without looking at the trace.
  • Change one input condition and explain whether the Heapify invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.