Heap Operations
The entire heap — push, pop, build — rests on two tiny helpers: sift-up and sift-down. Each is under ten lines. And there’s exactly one line people get wrong, every time, that silently corrupts the whole structure. Spot it and heaps become trivial; miss it and your “working” code returns wrong answers on the inputs you didn’t test.
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 = smallestAlso 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 upwardThe 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 minWhy 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.
Recall sift-down — compare BOTH children
Fill in the two lines that find the smaller child (the ones the shortcut above gets wrong):
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.
Quick check
You’ve got the four operations and the two primitives behind them. Next: the priority queue — the API every standard library actually exposes (you’ll rarely hand-roll the heap above), and how to store richer items than plain integers.