Inside the Heap: Sift Up, Sift Down

Inside push and pop

heapq hides the repair work behind three calls, but you should build push and pop once yourself, for two practical reasons. First, priority logic goes wrong in real systems (ties, stale entries, wrong sort keys), and you cannot debug a structure you have never seen the inside of. Second, the two repair moves — sift up and sift down — are the standard interview probe for whether you actually understand heaps, and implementing them proves the O(log n) claims from lesson 8-1 instead of taking them on faith.

Everything happens in the array form: the heap is a Python list where index i's children sit at 2i+1 and 2i+2, which flips around to say index i's parent sits at (i − 1) ⁄ 2, rounded down — in Python, (i - 1) // 2.

Push must keep the tree complete AND keep the heap promise (every node ≤ its children). Completeness dictates where the value goes: the first free slot on the bottom level, which in the array is simply append — the next free slot. That may put a small value under a bigger parent, breaking the promise at exactly one link. Sift up repairs it: while the new value is smaller than its parent, swap them and follow the value upward. Each swap climbs one level, and a complete tree has about log₂ n levels, so the loop runs at most that many times.

Pop and sift down

Pop removes the root, but the root's slot cannot simply be left empty — a hole at the top breaks both completeness and the array layout. Completeness allows removing only one position without creating a gap: the last array slot. So pop saves heap[0], moves the last element into the root's slot, and repairs downward.

Sift down: compare the moved value with its children and swap it with the smaller child, repeating until it is ≤ both children (or reaches the bottom). It must be the smaller child, because that child is about to become the parent of the other one — promote the larger child and the promise breaks instantly on the sibling link. Again one swap per level: O(log n).

One bonus falls out for free. Popping n times hands you the values in ascending order — n pops × O(log n) each = an O(n log n) sort. Done in place on the array, that algorithm is called heapsort, and the Algorithms course puts it next to merge sort and quicksort. You will build its engine right now.