Heapify Explained: Why Building a Heap Is O(n)

"What is the time complexity of building a heap?" is a trick question with a satisfying answer. Pushing n values one at a time costs O(n log n), and most people assume heapify must too, since every sift can take log n swaps. It does not. Building a heap bottom-up is O(n), and the reason is a counting argument you can explain in a few sentences.

The problem it solves

A binary min-heap is an array where every parent is no larger than its children: the children of index i sit at 2i + 1 and 2i + 2. That shape gives O(1) access to the minimum and O(log n) push and pop, which is why heaps power priority queues, top-k selection, Dijkstra and heap sort.

When you start with a whole array rather than a stream, you could push the values one by one, but heapify fixes the array in place, faster.

The intuition

Heaps are repaired by two moves, and each one walks a single path:

• Sift down: a value that is too big swaps with its smaller child until both children beat it or it reaches a leaf.
• Sift up: a value that is too small swaps with its parent until the parent beats it or it reaches the root.

Heapify sifts down every parent, starting at the last parent, index n // 2 - 1, and moving backwards to the root. The second half of the array is leaves, already valid one-element heaps. When you reach index i, both its subtrees are heaps, so only the value at i can be out of place, and one sift down fixes it.

Now the counting argument. A sift down costs at most the node's height, its distance to the bottom. About half the nodes are leaves with height 0, a quarter have height 1, an eighth height 2, and only the root has the full log n. The total is bounded by n: expensive nodes are rare and plentiful ones are nearly free.

Pushing one at a time is the mirror image. A sift up costs the node's depth, and half the nodes sit at the deepest level, so the total really is O(n log n) in the worst case.

Watch it run

The animation heapifies [9, 4, 7, 1, 3]. It starts as a raw pile, not a heap, and fixing it never touches the whole array: each wrong value walks one path. Indexes 3 and 4 are leaves; half the array is leaves, and a leaf has nothing to sift past. So it starts at the last parent, index 1, just above the bottom row, and works backwards. It compares 4 with the smaller of its children, 1; since 4 is greater than 1, it swaps and continues from the child's index, and that subtree is done. Then index 0. Its two subtrees are already heaps, so only the root value can be out of place. 9 is compared against the smaller child, 1, because the parent must beat both. It swaps and follows the value down, since 9 is still too big where it landed, and swaps once more with 3. The result is [1, 3, 7, 4, 9]: two sifts, three swaps, and the deepest values barely moved. That is why bottom-up heapify is O(n), not O(n log n): the many nodes near the bottom cost almost nothing.

The code

The lesson's sift down, counting swaps so the argument can be measured, and heapify as a loop from the last parent to the root. Python's heapq.heapify produces the same array here:

def sift_down(h, i, n=None):
    n = len(h) if n is None else n
    swaps = 0
    while 2 * i + 1 < n:                  # while a left child exists
        c = 2 * i + 1
        if c + 1 < n and h[c + 1] < h[c]:
            c += 1                        # take the smaller child
        if h[i] <= h[c]:
            break                         # parent already beats both
        h[i], h[c] = h[c], h[i]
        i = c                             # follow the value down
        swaps += 1
    return swaps

def heapify(h):
    swaps = 0
    for i in range(len(h) // 2 - 1, -1, -1):   # last parent first
        swaps += sift_down(h, i)
    return swaps

pile = [9, 4, 7, 1, 3]
print(heapify(pile), pile)                # 3 [1, 3, 7, 4, 9]

import heapq
other = [9, 4, 7, 1, 3]
heapq.heapify(other)
print(other)                              # [1, 3, 7, 4, 9]

The same worst-case input, a descending array where every value is in the wrong place, built both ways. Bottom-up stays below n swaps; pushing one at a time grows like n log n:

def sift_up(h, i):
    swaps = 0
    while i > 0 and h[i] < h[(i - 1) // 2]:
        p = (i - 1) // 2
        h[i], h[p] = h[p], h[i]
        i = p
        swaps += 1
    return swaps

def build_by_pushing(values):
    h, swaps = [], 0
    for v in values:
        h.append(v)
        swaps += sift_up(h, len(h) - 1)   # each push may climb the full height
    return h, swaps

for n in (1023, 65535):
    worst = list(range(n, 0, -1))         # descending: every value is in the wrong place
    print(n, heapify(list(worst)), build_by_pushing(worst)[1])
# 1023 1013 8194
# 65535 65519 917506

Heapify is also the first phase of heap sort: build once in O(n), then repeatedly swap the minimum to the end and sift the new root down inside the shrinking heap:

def heap_sort_desc(h):
    heapify(h)
    for end in range(len(h) - 1, 0, -1):
        h[0], h[end] = h[end], h[0]       # move the minimum out of the heap
        sift_down(h, 0, end)
    return h

print(heap_sort_desc([5, 2, 8, 1, 9, 3]))  # [9, 8, 5, 3, 2, 1]

Checked against a brute-force heap test and a plain sort on 3,000 random arrays, including duplicates and the empty array, with the swap count held to at most n:

import random

def is_min_heap(h):
    return all(h[(i - 1) // 2] <= h[i] for i in range(1, len(h)))

random.seed(21)
ok = True
for _ in range(3000):
    raw = [random.randint(0, 50) for _ in range(random.randint(0, 40))]
    h = list(raw)
    swaps = heapify(h)
    ok &= is_min_heap(h) and sorted(h) == sorted(raw)
    ok &= swaps <= len(raw)               # the O(n) bound, counted in swaps
    ok &= heap_sort_desc(list(raw)) == sorted(raw, reverse=True)
    pushed, _ = build_by_pushing(raw)
    ok &= is_min_heap(pushed) and pushed[:1] == sorted(raw)[:1]
print(ok)                                 # True

The complexity

• Heapify: O(n) time. The sum of node heights in a complete binary tree is less than n; for a perfect tree of 1,023 nodes it is exactly 1,013, the number printed above.
• Push one at a time: O(n log n) in the worst case, because the costs follow depth and most nodes are deep.
• Space: O(1) extra; the heap lives in the array it started in.
• After building: peek is O(1), push and pop are O(log n). The Big-O cheat sheet lists these next to the other structures.

Where it goes wrong

• Starting at the root. Sifting top-down from index 0 is wrong, not just slow: a value fixed early can be disturbed by a later swap below it.
• Swapping with the first child instead of the smaller one. Promote the larger child and it becomes the parent of a smaller value.
• Mixing min-heap and max-heap comparisons. Python's heapq is a min-heap; negate keys for a max-heap rather than flipping one comparison.
• Claiming heapify sorts the array. It only guarantees the parent rule. [1, 3, 7, 4, 9] is a heap and not sorted.

When it shows up in interviews

It comes up as a complexity question, inside heap sort, and whenever a solution heapifies an input before popping k times, as in k closest points to the origin. Implementing a priority queue from scratch means writing sift down and sift up by hand.

How to say it in an interview

"To build a heap from an array I sift down every parent, from the last one at n // 2 - 1 back to the root; leaves are already heaps, and when I reach a node both its subtrees are heaps, so one sift down fixes it. It is O(n), not O(n log n), because a sift down costs the node's height, and half the nodes have height zero, a quarter height one, and so on; the sum is bounded by n. Pushing values one by one is O(n log n), since sift up costs depth and most nodes are deep."