The Heap: Always Know the Minimum

One weak promise, huge payoff

Could we just keep the waiting list fully sorted? Sure, but inserting into a sorted array is O(n) shifting (lesson 2-3). The insight of the heap: you never need the whole line sorted. You only ever need the next item.

A min-heap is a binary tree that keeps one promise, the heap property:

every node ≤ its children.

That is much weaker than sorted, and that weakness is the speed. Nothing says the left child is smaller than the right. But the root must be the minimum of everything, because every path from the root only ever goes up in value.

A heap also fixes its shape. Lesson 7-3 just showed that a tree's height can degrade all the way to O(n), so a value promise alone is not enough. A heap is always a complete tree: every level is completely full except possibly the bottom one, and the bottom level fills strictly left to right, no gaps. Completeness pins the height, because each full level doubles the node count (1 + 2 + 4 + ...): n nodes can never stack more than about log₂ n levels, so a heap cannot degenerate into the tall chain that ruined the sorted-input BST.

• peek at the minimum: O(1), read the root
• push a value: place it in the first free slot on the bottom level (keeping the tree complete), swap it up while it beats its parent: O(log n) swaps, one per level
• pop the minimum: remove the root, move the last item up, swap it down: O(log n)

And one engineering gem: no gaps means the tree can live in a plain array, no pointers — read the levels top to bottom, left to right, into consecutive slots. The node at index i has children at 2i+1 and 2i+2, an address formula in the spirit of lesson 2-1.