"A heap maintains itself with two tiny moves: bubble a too-small element up toward the root, or sink a too-big one down toward the leaves. Every heap operation is just one of those two, repeated O(log n) times."
Push: Append, Then Sift Up
To insert into a heap: drop the new value at the end of the array (the next leaf, preserving completeness), then sift it up — while it's smaller than its parent, swap them, climbing toward the root. It stops when it's no longer smaller than its parent (or reaches the top). Since the climb is at most the height of the tree, push is O(log n). You're restoring the heap property along a single root-to-leaf path, not touching the rest of the heap.
Pop: Swap, Shrink, Sift Down
To remove the minimum (always the root): save the root, move the last element into the root slot, shrink the array by one, then sift it down — while it's larger than its smaller child, swap with that child, sinking toward the leaves. Again at most the height of the tree, so pop is O(log n). Peeking the min without removing is O(1) (just read index 0). Push and pop are mirror images: one bubbles up, one sinks down, both fix a single path.
Push = append at the end + sift up (O(log n)). Pop = take the root, move the last element up, + sift down (O(log n)). Peek = read index 0 (O(1)). Every heap operation restores order along one root-to-leaf path.
The Surprise: Building a Heap Is O(n), Not O(n log n)
Suppose you have an unordered array and want to turn it into a heap. The obvious way — push each element one at a time — costs O(n log n). But there's a beautiful faster way: sift down every node, starting from the last parent and working backward to the root. This builds a valid heap in O(n) — linear, not linearithmic. The intuition for why: most nodes are near the bottom (leaves are half the tree) and have tiny sift-down distances; only the few nodes near the root sift far. Summing those distances gives O(n), not O(n log n). It's a genuinely surprising result and a lovely example of how the order you do work in can change the complexity. (Python's heapq.heapify uses exactly this.)
Pippa's Confession
I was sure building a heap had to be O(n log n) — n insertions, each O(log n), obviously. Dad showed me the bottom-up sift-down and the O(n) proof, and I argued with him for ten minutes before the summation convinced me. The lesson that stuck: my 'obvious' complexity was counting the worst case for every node, when most nodes are leaves that barely move. Cost analysis rewards looking at the distribution of work, not assuming every step is the expensive one.
Code
Push, pop, and the O(n) build-heap·python
def sift_up(heap, i):
while i > 0:
p = (i - 1) // 2
if heap[i] < heap[p]: # smaller than parent? climb
heap[i], heap[p] = heap[p], heap[i]
i = p
else:
break
def push(heap, value): # O(log n)
heap.append(value) # add at the end (next leaf)
sift_up(heap, len(heap) - 1)
def sift_down(heap, i):
n = len(heap)
while True:
l, r, smallest = 2*i+1, 2*i+2, i
if l < n and heap[l] < heap[smallest]: smallest = l
if r < n and heap[r] < heap[smallest]: smallest = r
if smallest == i: break
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
def pop_min(heap): # O(log n)
heap[0], heap[-1] = heap[-1], heap[0] # swap root with last
m = heap.pop() # remove old root from the end
if heap: sift_down(heap, 0)
return m
def build_heap(arr): # O(n) — the surprise!
for i in range(len(arr)//2 - 1, -1, -1): # last parent -> root
sift_down(arr, i)
return arr
h = []
for x in [5, 3, 8, 1, 9, 2]: push(h, x)
print("pops:", [pop_min(h) for _ in range(6)]) # [1, 2, 3, 5, 8, 9] sorted!
print("O(n) build:", build_heap([5, 3, 8, 1, 9, 2])) # a valid heap, root=min
Start with the min-heap [1, 4, 2, 8, 5] and push the value 3. Trace the sift-up step by step: where does 3 land first, and which swaps happen until the heap property is restored? Then state why push is O(log n) and not O(n).
Hint
3 is appended at index 5; its parent is index 2 (value 2). 3 > 2, so no swap needed — it stops immediately. Push is O(log n) because sift-up climbs at most the tree's height (one root-to-leaf path), never scanning the whole array.
Progress
Progress is local-only — sign in to sync across devices.