How Does Heapify Work?

A heap is stored as a complete binary tree in a plain array, so the children of the node at index i live at two i plus one and two i plus two. Heapify works from the bottom up: start at the last non-leaf node and sift each one downwards, and by the time you reach the root the whole array satisfies the heap invariant.

It is linear rather than quadratic because most of the nodes are near the bottom and have almost nothing to sift, and the total amount of sifting is proportional to the number of nodes.

def sift_down(data, start, n):
    root = start
    while True:
        child = 2 * root + 1
        if child >= n:
            return
        if child + 1 < n and data[child + 1] < data[child]:
            child += 1
        if data[child] >= data[root]:
            return
        data[root], data[child] = data[child], data[root]
        root = child


def heapify(values):
    data = list(values)
    n = len(data)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(data, i, n)
    return data


print(heapify([5, 3, 8, 1, 2, 7]))

The output is 1, 2, 7, 3, 5, 8. The first element is the smallest, and every parent is no greater than its children, which is the min heap invariant.

The mechanism is the bottom up order. The last non-leaf node is at index n divided by two minus one, and sifting from there means that when you reach a node, both of its subtrees are already valid heaps, so the single sift down repairs the whole subtree under it.

The trade-off to name is that pushing every element into an empty heap one at a time is logarithmic per element and therefore linear in total as well, but with a much worse constant because of the repeated sifting. The classic interview trap is asking whether heapify is linear or logarithmic: building a heap by repeated pushes is linear overall but does more work than heapify does.

Sift up moves a value towards the root by swapping it with its parent for as long as it is smaller than that parent. It is the operation used when a new element is appended to the end of the array.

def sift_up(data, index):
    while index > 0:
        parent = (index - 1) // 2
        if data[parent] <= data[index]:
            return
        data[parent], data[index] = data[index], data[parent]
        index = parent


data = [1, 2, 7, 3, 5, 8]
data.append(0)
sift_up(data, len(data) - 1)
print(data)

The output is 0, 2, 1, 3, 5, 7, 8. The new zero was appended at the end and then swapped upwards three times until it reached the root, which is the correct place for the smallest value in a min heap.

The mechanism is the parent index, which is the position minus one divided by two. Because the parent of a node at index i is always at a smaller index, swapping the node with its parent moves it up while keeping the tree shape intact. The loop stops as soon as the parent is no larger than the value.

The trade-off to name is that sift up only makes sense for a value that was just added at the end of the array. Running it on a value that already has children would break the invariant, because the value you displace would land where it is larger than its own children. That is why an insertion appends and then sifts up, and why removing the root instead sifts down. Both operations are bounded by the height of the tree, so each is logarithmic.

A heap is a list plus the two operations that restore the invariant. Push appends and sifts up. Pop removes the root, moves the last element into its place and sifts that down.

class MinHeap:
    def __init__(self):
        self.items = []

    def push(self, value):
        self.items.append(value)
        self._sift_up(len(self.items) - 1)

    def pop(self):
        if not self.items:
            return None
        top = self.items[0]
        last = self.items.pop()
        if self.items:
            self.items[0] = last
            self._sift_down(0)
        return top

    def peek(self):
        return self.items[0] if self.items else None

    def _sift_up(self, index):
        while index > 0:
            parent = (index - 1) // 2
            if self.items[parent] <= self.items[index]:
                return
            self.items[parent], self.items[index] = self.items[index], self.items[parent]
            index = parent

    def _sift_down(self, index):
        n = len(self.items)
        while True:
            child = 2 * index + 1
            if child >= n:
                return
            if child + 1 < n and self.items[child + 1] < self.items[child]:
                child += 1
            if self.items[index] <= self.items[child]:
                return
            self.items[index], self.items[child] = self.items[child], self.items[index]
            index = child


heap = MinHeap()
for value in [5, 3, 8, 1]:
    heap.push(value)
print(heap.peek())
print(heap.pop())
print(heap.items)

The outputs are 1, then 1, then the list 5 and 8. The smallest value pushed was 1, it was the first thing popped, and afterwards the heap holds 5 and 8 in a valid arrangement.

The mechanism is that the array representation gives constant time access to both children and the parent, so each sift is a loop of swaps along a single path. The push path walks up from a leaf to the root and the pop path walks down from the root to a leaf, and both paths have length at most the height of the tree, which is logarithmic in the number of elements.

The trade-off to name is that writing your own heap is only worth it when you need control over the behaviour, because the standard library already provides heapq and its functions are implemented in C and therefore faster in practice. The hand written version is still worth understanding once, because the invariant and the two sift operations are the foundation of every heap based problem, and because it lets you add things like a stable key or a count that the library does not support. In production, reach for heapq.