Inside push and pop
heapq hides the repair work behind three calls, but building push and pop once yourself is worth the effort for two practical reasons.
First, priority logic goes wrong in real systems through ties, stale entries, and wrong sort keys, and a structure you have never seen the inside of is a structure you cannot debug. Second, the two repair moves, sift up and sift down, are the standard interview probe for whether you understand heaps, and implementing them proves the O(log n) claims from lesson 8-1 rather than 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, and inverting that formula says index i's parent sits at (i − 1) ⁄ 2 rounded down, written (i - 1) // 2 in Python.
Push has to satisfy both rules at once, keeping the tree complete and keeping the promise that every node ≤ its children.
Completeness decides the location with no freedom at all. The value belongs in the first free slot on the bottom level, which in the array is simply the next free slot, so append does it.
That placement may drop a small value under a bigger parent, which breaks the promise at exactly one link and nowhere else. Sift up repairs it by swapping the new value with its parent while it is smaller, following it upward.
Each swap climbs one level, and a complete tree has about log₂ n levels, so the loop can run at most that many times.
Push, built by hand
Append, then climb while the value beats its parent.
def push(heap, value): heap.append(value) i = len(heap) - 1 while i > 0: parent = (i - 1) // 2 if heap[i] < heap[parent]: heap[i], heap[parent] = heap[parent], heap[i] i = parent else: break heap = [] for v in [7, 4, 9, 1]: push(heap, v) print("after push", v, "->", heap)
Output
after push 7 -> [7] after push 4 -> [4, 7] after push 9 -> [4, 7, 9] after push 1 -> [1, 4, 9, 7]
The while i > 0 condition is the stopping rule at the top, since index 0 has no parent to compare against. The break is the other exit, taken as soon as the promise holds, which is why most pushes cost far less than log₂ n swaps.
The last line is the one to trace. Pushing 1 appends it at index 3, whose parent is (3 − 1) // 2 = 1, so it swaps past the 7 sitting there, then compares against index 0 and swaps past the 4 to reach the root.
Reading [1, 4, 9, 7] as a tree confirms it. The root is 1, its children at indexes 1 and 2 are 4 and 9, and 4's left child at index 3 is 7, so every parent is ≤ its children.
Notice that pushing 9 changed nothing beyond the append. It landed at index 2 under the root 4, the promise already held, and the loop broke on its first comparison.
The parent of index 9 is at (9 − 1) // 2 = 4, and push uses append because the next free array slot is exactly the next left-to-right position on the bottom level.
The parent formula is just the child formula read backwards. Children of i live at 2i+1 and 2i+2, so index 9 must be a child of 4, and checking forwards confirms it, since node 4's children are 9 and 10.
The integer division is what makes one formula serve both children. Index 9 and index 10 both map back to 4, which is correct, because a parent has two children and only one parent slot to point back at.
A tempting wrong answer is 2 × 9 + 1 = 19, which is node 9's left child. That is the formula pointed the wrong way, and it is the most common slip when working in the array form.
As for append, the array stores levels top to bottom and left to right with no gaps, so the end of the list is always the next position completeness demands. Preserving the shape therefore costs no thought and no extra code.
Pop and sift down
Pop removes the root, but the root's slot cannot simply be left empty, since a hole at the top breaks both completeness and the array layout.
Completeness allows exactly one position to be removed without creating a gap, and that is the last array slot. So pop saves heap[0], moves the last element into the root's slot, and repairs downward from there.
Sift down compares the moved value with its children and swaps it with the smaller child, repeating until it is ≤ both children or reaches the bottom.
The smaller child is not a preference. That child is about to become the parent of the other one, so promoting the larger of the two would break the promise instantly on the sibling link, and the repair would leave the heap invalid in a new place.
Again the work is one swap per level, which is O(log n).
One bonus falls out for free. Popping n times hands back the values in ascending order, so n pops at O(log n) each is an O(n log n) sort.
Done in place on the array, that algorithm is called heapsort, and the Algorithms course sets it beside merge sort and quicksort. Its engine is the function in the next block.
Pop, built by hand
Save the root, move the last element up, then sift down.
def pop(heap): top = heap[0] last = heap.pop() if heap: heap[0] = last i = 0 n = len(heap) while True: left, right = 2 * i + 1, 2 * i + 2 smallest = i if left < n and heap[left] < heap[smallest]: smallest = left if right < n and heap[right] < heap[smallest]: smallest = right if smallest == i: break heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest return top heap = [1, 4, 5, 9, 7, 8] out = [] while heap: out.append(pop(heap)) print("pop order:", out)
Output
pop order: [1, 4, 5, 7, 8, 9]
The smallest variable starts at i and is updated only by a strictly better candidate, which finds the minimum of the three positions in two comparisons without a separate case for each shape.
Both child checks are guarded with < n, and that guard is not optional. Bottom-level nodes may have one child or none, so an unguarded heap[left] would read past the end of the list.
if smallest == i: break is the success condition. Nothing beat the current value, so the promise holds and the walk stops, usually well before the bottom.
The empty-heap case is handled by if heap: after the heap.pop(). Popping the last element empties the list, and skipping the repair matters because heap[0] = last would otherwise put the value straight back.
The ascending output is the proof that the repair is correct. Every pop returned the true minimum of what remained, which means a working pop is already a working sort.
It must swap with 12 because whichever child moves up becomes the other child's parent, so it has to be the smaller one.
Promoting 12 leaves links that read 12 ≤ 20 and 12 ≤ 30, both satisfied, so the heap is valid at that node.
Promoting 30 puts 30 directly above 12, which breaks the promise immediately on a link the swap never even looked at. The original problem would be fixed and a new one created one level up.
That is why the smaller-child rule is a correctness requirement rather than an optimization. It is also the reason the code computes smallest across all three positions instead of stopping at the first child that beats the value.