Implement Max Heap
Build a max-heap from scratch: push, pop-max, and heapify on a plain array.
Intuition
A heap is a complete binary tree flattened into an array: children of i live at 2i+1 and 2i+2. Only one rule — parent ≥ children. Push bubbles a new leaf up; pop moves the last leaf to the root and sifts it down. Everything is swaps along one root-to-leaf path.
A heap is an array pretending to be a tree: children of i live at 2i+1 and 2i+2, the parent at (i-1)//2. Insertion bubbles up, removal moves the last element to the root and sinks it down. Both operations restore the invariant along a single root-to-leaf path, which is why they're O(log n).
Approach
Array as tree
Completeness means no gaps: parent(i) = (i−1)//2. No pointers, great cache behaviour.
sift-up on push
Append at the end; swap with the parent while bigger than it. At most log n swaps.
sift-down on pop
Replace root with the last element; repeatedly swap with the larger child while smaller than it. Build-heap runs sift-down from n//2−1 backwards — O(n) total.
Solution & live demo
Common pitfalls
Using the wrong parent formula
parent = i // 2
parent = (i - 1) // 2
i // 2 is the parent formula for a 1-indexed heap. With 0-based arrays the children of i are 2i+1 and 2i+2, which inverts to (i-1)//2. Mixing the conventions silently compares against the wrong node.
Removing the root directly on pop
a.pop(0)
top, last = a[0], a.pop() if a: a[0] = last; # sink down
pop(0) shifts every element — O(n) — and destroys the heap layout. The standard move is to lift the last element into the root and sink it, which touches only one path.
Comparing against i instead of the running best when sinking
if l < n and a[l] > a[i]: big = l if r < n and a[r] > a[i]: big = r
if l < n and a[l] > a[big]: big = l if r < n and a[r] > a[big]: big = r
The second test must run against the winner of the first, not the original parent. Comparing both to a[i] lets the right child overwrite a larger left child, so the smaller of the two is promoted and the heap property breaks.
Edge cases
Root is the last element — remove and return, no sift.
≥ comparisons make ties stable enough; heap order tolerates equals on either side.