A thousand numbers,
one honest promise

A heap is a complete binary tree with a single rule: every parent beats its children. In a min-heap the parent is smaller; in a max-heap, bigger. That's the whole contract. Siblings are in no particular order, cousins are in no particular order — walk the tree left to right and you get near-nonsense. The only element with a guaranteed address is the root: the minimum (or maximum) of everything, readable in O(1).

"Complete" means every floor is full except possibly the last, which fills left to right. That shape buys two things. First, the tree is never taller than ⌈log₂ n⌉ floors, so any root-to-leaf walk is O(log n) — one short path, even for a million elements. Second, you don't need pointers at all: lay the levels into a plain array, and the children of index i live at 2i+1 and 2i+2, the parent at (i−1)/2. Navigation is arithmetic. Every heap you'll ever use — Python's heapq, Scala's PriorityQueue — is secretly a flat array doing index math.

Only two operations ever disturb the promise, and each has a one-word repair:

• Push. Append the newcomer at the end of the array (the next free leaf), then sift up: while it beats its parent, swap. It bubbles up its ancestor chain until the rule holds again.
• Pop. The root leaves. Move the last leaf into the hole (keeping the tree complete), then sift down: while some child beats it, swap with the winning child. It sinks until the rule holds.

Both repairs walk a single root-to-leaf path, so both are O(log n) — one short walk, never a full re-sort. Push and pop below and watch the comparison counter: even on a full four-floor heap, an operation costs a handful of comparisons, not fifteen.

One free lunch worth naming: building a heap from n existing items is not n pushes at O(n log n). Sift down from the middle of the array backwards and the total is O(n) — most elements are near the leaves and barely move. Python's heapq.heapify does exactly this. If all the data is already in hand, heapify first and thank yourself later.

Here's the pattern's flagship move, and it's deliberately counterintuitive: to keep the k largest elements, use a min-heap of size k.

Think of the heap as a VIP room with k seats and a bouncer. The room holds the k best seen so far; the bouncer is the worst of the keepers — and in a min-heap of the keepers, that's exactly who sits at the root, readable in O(1). Each new arrival gets one question: do you beat the bouncer? No → walk away, nothing changes. Yes → the bouncer is evicted (pop), the newcomer takes a seat (push), and a new worst-keeper rises to the door. Stream all n elements past the room and the k survivors are your answer, with the kth largest conveniently standing at the root.

The cost: n arrivals, each at most one pop and one push into a heap that never exceeds k — O(n log k), "one pass, paying log of the small number". For n = 10⁶ and k = 10, that's the difference between ~20 million comparisons for a full sort and ~3 million — and you never needed all n elements in memory at once, which is why this trick survives even when the input is a stream you can't rewind.

The family, by their real names:

• Kth Largest Element in an Array Medium — the trick verbatim: min-heap of size k, answer at the root.
• K Closest Points to Origin Medium — keep the k smallest distances, so flip it: a max-heap of size k, bouncer = farthest keeper.
• Top K Frequent Elements Medium — Chapter 4's hash map counts frequencies, then a size-k heap picks the winners. Two patterns shaking hands.
• Last Stone Weight Easy — no size-k trick, just the raw promise: pop the two heaviest, smash, push the remainder, repeat. A max-heap doing honest work.

You will never hand-roll a heap in an interview (though section 2 means you could). You'll reach for the library — and the two libraries this book speaks have opposite defaults, which is a classic source of silent bugs:

• Python: heapq is functions over a plain list, and it is min-heap only. Need a max-heap? Push negated values — heappush(h, -x) — and negate again on the way out. Ugly, universal, expected.
• Scala: mutable.PriorityQueue is a max-heap by default. Need a min-heap? Pass Ordering[Int].reverse. Same trick, politer syntax.

Two more shelf habits worth having. Pushing tuples works — (dist, x, y) compares by distance first — but make sure a tie on the first field can't force a comparison of incomparable second fields; when in doubt, put an index in slot two as a tiebreaker. And when the data is all present up front, remember section 2's free lunch: heapify in O(n), then pop.

The median is a strange target for a heap: it's the middle, and heaps only promise edges. The move — one of the prettiest in the entire catalogue — is to make the middle be an edge. Split everything seen so far into two halves:

• low — the smaller half, kept in a max-heap, so its largest member is on top;
• high — the larger half, kept in a min-heap, so its smallest member is on top.

The two roots now face each other across the median line. Keep two invariants — every element of low ≤ every element of high, and the sizes differ by at most one — and the median is always at arm's length: the root of the bigger heap, or the average of both roots when they tie. That's Find Median from Data Stream Hard, and the Hard is entirely in seeing the trick; the code is a dozen lines.

The insertion policy that keeps both invariants without case analysis is the routing trick: push the newcomer into low, then move low's top across to high — this guarantees the ordering invariant, because whatever crosses is certified ≥ everything left in low. Then, if high got too big, send its top back. Every insert is two or three O(log n) heap moves, and the median read is O(1). Stream numbers into the seesaw below and watch the halves stay balanced:

Merge K Sorted Lists Hard hands you k lists, each already sorted, and asks for one sorted output. The two-list merge from Chapter 10 zips with two fingers; with k lists you'd need k fingers, and the question every step is the same: which finger points at the smallest value right now?

"Repeatedly ask for the smallest of a changing set" — that's the heap's one promise, verbatim. So heap the fronts: a min-heap holding one entry per list, (head value, which list). Each round, pop the winner, append it to the output, advance that list one node, and push its new head. The heap never holds more than k entries — it's a heap of iterators, not of data — so n total nodes cost O(n log k): every node pays one heap visit priced by the tiny k, not by n. Run the conveyor:

Three tools bid on every top-k problem, and choosing between them out loud is cheap interview credit:

• Sort everything: O(n log n) — "sort once, take a slice". Simplest to write, buys far more order than you asked for, needs all data present. Perfectly acceptable to mention first as the brute-force baseline.
• Size-k heap: O(n log k), O(k) extra space, and — the killer feature — streaming. When k ≪ n, log k is effectively constant; when the data won't fit in memory, this is the only bidder left standing.
• Quickselect: O(n) average — partition like quicksort but recurse into one side only. Fastest on paper for a one-shot "kth element", but offline (needs the whole array, mutates it), O(n²) worst case, and it produces the kth element, not a maintained top-k set.

The deciding question is almost always "is the data all here, once, or arriving forever?" One-shot and in memory: sort or quickselect are fine, and for Top K Frequent there's even a cute O(n) bucket-sort-by-count answer. Streaming, or asked to maintain the answer as data changes: heap, no contest — which is exactly why Kth Largest Element in a Stream exists as a problem: it's the size-k heap wearing no costume at all.

And the heap has a second career ahead of it: Chapter 17's Dijkstra is just Chapter 15's BFS with the queue upgraded to a min-heap, so the cheapest frontier node expands first. Same promise, bigger stage. Meanwhile its cousin the monotonic deque (Chapter 8) undercuts it on one specific job — Sliding Window Maximum in O(n) — a good reminder that "maximum of a moving window" and "maximum of a growing pile" are different sentences.

Every problem in this chapter reduces to three decisions: how many heaps (one, one capped at k, or two), which kind (min or max — for top-k, the opposite of the superlative in the problem), and what lives inside (values, tuples keyed by a metric, or per-source iterators). Make those three calls from the problem statement and the code writes itself — the loop body is never more than four lines.

Rehearse the mapping until it's a reflex: extreme, repeatedly → one heap. k best of a flood → size-k heap of the opposite kind. middle of a stream → two heaps facing each other. k sorted sources, one order → heap of fronts. Anything about a contiguous window's extreme → not here, Chapter 8's deque.

The pattern, as a whiteboard skeleton:

1. 1Hear the trigger words — "k largest / k closest / kth / median of a stream / merge k sorted" — and say "heap" before touching the keyboard.
2. 2Name the repeated question the structure must answer ("smallest current front", "worst current keeper") — that question's answer is what sits at the root.
3. 3Pick the kind by opposites: keep the k largest → min-heap; keep the k smallest → max-heap. The root is the bouncer — the worst keeper, first to be evicted.
4. 4Cap it: push, then pop whenever size exceeds k. The heap must never grow past k, or you've silently paid log n.
5. 5Median variant: two heaps — low as max-heap, high as min-heap; route every insert low → high, then rebalance if sizes differ by two.
6. 6Merge variant: heap of (value, source) fronts; pop → output → advance that source → push its next head.
7. 7Mind the library: Python heapq is min-only (negate for max, matched signs at the doorway); Scala PriorityQueue is max-first (reverse the Ordering for min); tuples need tiebreakers.
8. 8State the price: O(n log k) — and say in one breath why it beats the O(n log n) sort and survives streaming input.

Find Median from Data Stream Hard is the chapter's flagship because it uses everything at once: two heaps of opposite kinds, the routing trick that maintains both invariants with zero case analysis, and (in Python) the negation discipline from section 4. Note the shape of addNum — push into low, hand low's top across to high, then rebalance if high outgrew low. Three heap moves, worst case, per arriving number: O(log n) insert, O(1) median, forever.

Read the two versions side by side: they are the same four decisions in different clothes. Python fakes its max-heap with minus signs; Scala just hands PriorityQueue a reversed Ordering. Narrating that difference in an interview — "heapq is min-only, so low stores negatives, and every read of it wears a minus" — is exactly the fluency signal Chapter 1 talked about.