Heap Operations

A binary heap has four operations worth memorizing. All of them are short — under ten lines of real code — and they all rely on two helper routines: sift-up and sift-down. Once you have those two, everything else falls out.

We’ll build a min-heap throughout this page. Swap every < for > and you have a max-heap; the structure is identical.

The two primitives: sift-up and sift-down

When we mess with the heap (insert at the end, replace the root), we temporarily violate the heap property at one node. We then “sift” that bad node up or down until the property is restored.

Sift-up

Used after we add a new element at the end of the array. Compare the new element to its parent; if it’s smaller, swap; repeat until you stop being smaller (or you reach the root).

sift_up(i):
    while i > 0 and heap[i] < heap[parent(i)]:
        swap heap[i] and heap[parent(i)]
        i = parent(i)

At most O(log n) swaps — that’s the height of the tree.

Sift-down

Used after we replace the root. Compare the bad node to both children; if it’s larger than the smaller child, swap with that child; repeat.

sift_down(i):
    while True:
        l = 2*i + 1, r = 2*i + 2
        smallest = i
        if l < n and heap[l] < heap[smallest]: smallest = l
        if r < n and heap[r] < heap[smallest]: smallest = r
        if smallest == i: return
        swap heap[i] and heap[smallest]
        i = smallest

Also O(log n). Crucially: we always compare against both children and swap with the smaller one. Swapping with the wrong child can re-break the heap property.

⚠️

The single most common bug in heap code: only checking one child in sift-down. If the right child is smaller than both the node and the left child, but you only swap with the left, the heap is now corrupted. Always check both.

1. Push (insert)

Stick the new element at the end of the array, then sift it up.

The algorithm

push(val):
    heap.append(val)         // append at the bottom-right of the tree
    sift_up(len(heap) - 1)   // restore heap property upward

The intuition

Adding at the end keeps the complete-tree shape: we extend the last level (or start a new one) from the left. The shape is fine. Now we just need to bubble up if the new value is smaller than its parent.

Code

Time: O(log n) — at most we swap our way from the leaf to the root.

2. Pop (extract min)

Pop the root — that’s the minimum. Replace it with the last element, then sift that down to restore the heap.

The algorithm

pop():
    if heap is empty: error
    min = heap[0]
    heap[0] = heap.pop_back()   // move the last element to the root
    sift_down(0)
    return min

Why we move the last element to the root

Popping the root leaves a hole. We can’t just shift everything up by one — that would scramble the structure. Instead, we put the last element in the root slot. That keeps the shape complete. Then we sift down.

Code

Time: O(log n) — at most we swap from the root to a leaf.

3. Peek

Just return heap[0]. If the heap is empty, decide whether you want an exception or a sentinel.

def peek(self):
    if not self.heap:
        return None
    return self.heap[0]

Time: O(1). This is the operation you actually came to the heap for.

4. Heapify (build heap from an array)

You’d think building a heap from n random elements would cost n × O(log n) = O(n log n) — push each one in turn. It can be done in O(n).

The trick: don’t push from empty. Start with the whole array already there (it’s a valid complete tree, just not a valid heap), and sift down every non-leaf node starting from the last one and working back to the root.

The algorithm

heapify(arr):
    for i from (n / 2 - 1) down to 0:
        sift_down(i)

Indices n/2 through n-1 are leaves — they don’t have children, so they’re already valid one-node “heaps.” We only need to fix the inner nodes.

Why it’s O(n) and not O(n log n)

It looks like we call sift-down n/2 times, each costing O(log n), so the total is O(n log n). The naive analysis is correct as an upper bound — but it’s loose.

The deeper truth: most nodes are near the bottom, where sift-down is cheap. Half the nodes are leaves (zero work). A quarter are one level up (at most one swap). An eighth are two levels up. And so on.

The sum is:

T(n) = (n/2)·0 + (n/4)·1 + (n/8)·2 + (n/16)·3 + ...  =  O(n)

You can pop a heap one element at a time to get a sorted array — that’s Heap Sort, and it costs O(n log n) overall. But building the heap itself is O(n). That asymmetry is what makes heaps useful when you only need the top few of many.

Code

Putting it all together

Summary of every operation, with the right intuition for each:

Operation	Cost	Where the work happens
peek	O(1)	Return root
push	O(log n)	Append + sift-up
pop	O(log n)	Save root, move last to root, sift-down
heapify	O(n)	Sift-down on all internal nodes, back-to-front

That’s the entire heap API. The rest of this chapter is just consequences.

Next: how to actually use a heap in real code. Every modern language ships one — and you should rarely write your own.

Introduction Priority Queues