The Heap Awakens: Building a Heap in O(n) Time

The Quest Begins (The “Why”)

I still remember the first time I tried to solve “find the K largest numbers in an unsorted array” during a mock interview. My naïve solution was to sort the whole thing and slice off the top K – O(n log n) time, O(n) space. The interviewer raised an eyebrow and asked, “Can we do better?” I felt like a kid trying to defeat a final boss with a wooden sword.

That moment sparked a quest: What if we could organise the data in linear time, then answer the query in a flash? The answer lay in a humble data structure we often overlook – the heap – and, more specifically, the build‑heap (heapify) procedure that turns any array into a valid heap in O(n).

The Revelation (The Insight)

So why does heap‑ify work in linear time? Let’s break it down like we’re dissecting a magic trick.

A binary heap is just an array that satisfies the heap property: every parent node is ≥ (max‑heap) or ≤ (min‑heap) its children. If we start from the leaves and work our way up, each leaf is already a heap of size 1 – trivially correct.

Now consider an internal node i. Its left and right sub‑trees are already heaps (because we processed them first). To fix the heap property at i we only need to sift‑down the element at i until it’s larger than both children (for a max‑heap). The sift‑down operation moves the node down at most the height of the sub‑tree rooted at i.

Here’s the magic: the height of a node decreases as we move upward. The total work is the sum over all nodes of their heights. In a complete binary tree with n nodes, this sum is bounded by 2n – yes, O(n). Intuitively, most nodes are near the bottom and have tiny heights; only a few nodes near the root have large heights, but there aren’t many of them.

That’s why we can heapify an entire unsorted array in linear time – no sorting, no extra passes, just a clever bottom‑up sift‑down.

Wielding the Power (Code & Examples)

The Struggle: Naïve Insertion

def heap_push(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        p = (i - 1) // 2
        if heap[p] >= heap[i]:          # max‑heap condition
            break
        heap[p], heap[i] = heap[i], heap[p]
        i = p

If we call heap_push for every element of an input list, we pay O(log n) per insertion → O(n log n) overall.

The Victory: Bottom‑Up Heapify

def sift_down(heap, start, end):
    """Move the element at `start` down until the heap property holds."""
    root = start
    while True:
        child = 2 * root + 1          # left child index
        if child > end:
            break
        # pick the larger child
        if child + 1 <= end and heap[child] < heap[child + 1]:
            child += 1
        if heap[root] >= heap[child]:
            break
        heap[root], heap[child] = heap[child], heap[root]
        root = child

def heapify(arr):
    """Transform `arr` into a max‑heap in-place, O(n)."""
    n = len(arr)
    # start from the last parent and move upwards
    for start in range((n // 2) - 1, -1, -1):
        sift_down(arr, start, n - 1)
    return arr

Why this is better:

• No extra auxiliary array – we work in‑place.
• Each sift_down touches at most the height of its sub‑tree; the total across all calls is linear.

Real Interview Problems

1. Find the K Largest Elements

def k_largest(nums, k):
    heapify(nums)                     # O(n)
    # repeatedly extract the max k times
    for i in range(k):
        nums[0], nums[-1 - i] = nums[-1 - i], nums[0]  # swap max to end
        sift_down(nums, 0, len(nums) - 2 - i)          # restore heap
    return nums[-k:]                  # the k largest, sorted ascending

• Building the heap: O(n)
• Each extraction: O(log n), done k times → O(k log n)
• Overall: O(n + k log n) – optimal when k is much smaller than n.

2. Sort a Nearly Sorted Array (distance ≤ d)

If every element is at most d positions away from its sorted spot, we can keep a min‑heap of size d+1 and slide through the array:

import heapq

def sort_almost_sorted(arr, d):
    heap = arr[:d+1]
    heapq.heapify(heap)               # O(d)
    result = []
    for i in range(d+1, len(arr)):
        result.append(heapq.heappop(heap))   # O(log d)
        heapq.heappush(heap, arr[i])         # O(log d)
    # drain remaining
    while heap:
        result.append(heapq.heappop(heap))
    return result

• Heapify of the first window: O(d)
• Each of the n‑d steps does a pop & push: O(log d)
• Total: O(n log d) – when d is small, this is practically linear.

Both problems show how the linear‑time heapify unlocks faster solutions than naïve sorting.

Why This New Power Matters

Now you’ve got a tool that lets you take an unordered mess and turn it into a priority‑ready structure in a single sweep. No more “sort first, then pick” mental gymnastics. You can:

• Stream data and maintain top‑K scores in real time.
• Implement Dijkstra’s or Prim’s algorithm with confidence that the priority queue initialization won’t dominate the runtime.
• Tackle coding‑interview questions that explicitly ask for “better than O(n log n)” and smile, knowing you’ve got the O(n) trick up your sleeve.

The best part? The code is short, uses only the array you already have, and works in‑place. It’s the kind of insight that makes you feel like you’ve just unlocked a secret level in a game—except the boss is a tricky algorithm, and you just defeated it with a clean, elegant move.

Your Turn

Grab an array of random integers, heapify it, and then try to extract the median using two heaps (a max‑heap for the lower half, a min‑heap for the upper half). Notice how the initial heapify step keeps the whole thing linear.

Challenge: Implement the “running median” problem using the heapify trick for the initial batch of numbers, then stream the rest. Share your solution or a question in the comments—I’m excited to see how you wield this new power!

---

P.S. If you ever feel stuck, remember: even Neo had to learn to dodge bullets before he could see the code. Keep sifting down, and you’ll rise.