Building Efficiently: The Bottom-Up Approach

Imagine you are restructuring a massive corporation. You have two options:

1. The “One-by-One” Approach (Insert): You hire one employee at a time, calculate their exact rank, and shift the entire management chain to accommodate them. Doing this for every single employee takes a massive amount of time—O(N log N).
2. The “Bottom-Up” Approach (Heapify): You gather all employees at once, group them into their local teams (leaves), and only fix management conflicts locally, moving up the chain. Since most people are at the bottom and need zero adjustments, the total restructuring time drops drastically to O(N).

When we already have all the elements (like an unsorted array), we can build a heap in O(N) time using a process called Heapify. This is the secret engine that makes Heap Sort so efficient.

---

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 ċ h = N/2 Σ h ċ (1/2)^h. This is a convergent geometric series. The sum Σ_h=0^∞ h/2^h goes to 2.

• Total Cost: N/2 ċ 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
  }
}

// Sift Down (Max Heap)
func heapify(arr []int, n int, i int) {
  largest := i
  left := 2*i + 1
  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 {
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest) // Recursively fix the affected subtree
  }
}