Heap Fundamentals & Top-K Pattern

Why this matters more than it seems

A heap is the answer whenever an interviewer's problem contains a disguised version of "give me the current smallest/largest thing, repeatedly, as the data set changes." That phrasing covers scheduling, streaming top-K, event simulation, and — later in this roadmap — Dijkstra's shortest-path algorithm in the Graphs topic. If you've internalized Sorting and Binary Search already, think of a heap as the data structure that gives up full ordering to get O(log n) insert/remove instead of paying O(n log n) to re-sort after every change.

What a heap actually is

A binary heap is a complete binary tree (every level fully filled except possibly the last, which fills left-to-right) that satisfies the heap property:

• Min-heap: every parent is ≤ both of its children. The minimum is always at the root.
• Max-heap: every parent is ≥ both of its children. The maximum is always at the root.

Crucially, a heap is not a sorted structure — siblings have no defined order relative to each other, only relative to their parent. That's exactly the relaxation that makes heap operations cheaper than keeping a fully sorted array.

Because the tree is complete, you never need pointers: it can be stored compactly in a plain array. For a node at index i (0-indexed):

• Parent: (i - 1) // 2
• Left child: 2*i + 1
• Right child: 2*i + 2

This array representation is what every standard library heap (Python's heapq, Java's PriorityQueue, C++'s std::priority_queue) uses under the hood — there is no explicit tree with node objects.

Core operations

Operation	What happens	Complexity
Peek min/max	Return heap[0]	O(1)
Push	Append to the end, then sift up (swap with parent while it violates the heap property)	O(log n)
Pop min/max	Swap root with the last element, remove the last element, then sift down (swap with the smaller/larger child while it violates the heap property)	O(log n)
Build heap from n elements	See below	O(n)

Building a heap in O(n) — the classic gotcha

If you push n elements one at a time, you pay O(log n) per push, for O(n log n) total. But if you already have all n elements up front, you can build the heap in O(n), not O(n log n). This surprises most candidates the first time they see it, and it's a great fact to drop in an interview to signal depth.

The trick (Floyd's build-heap algorithm): call sift-down on every non-leaf node, starting from the last non-leaf (n // 2 - 1) and working backward to the root — never sift up from the leaves.

Why is this O(n) and not O(n log n)? A naive bound says "n nodes, each sift-down costs O(log n)," giving O(n log n) — but that bound is loose. The key insight: most nodes are near the bottom of the tree, where a sift-down is cheap (a leaf does zero work; a node one level up does at most one swap). Only the O(1) nodes near the root can sift all the way down O(log n) levels. Summing the actual work over all levels gives a geometric-like series that converges to O(n) total, not O(n log n). Python's heapq.heapify, Java's bulk PriorityQueue(Collection) constructor, and C++'s make_heap all use this in O(n) — but pushing elements one at a time into an empty heap does not get you this speedup, since each push only ever sifts up from a single new leaf.

Min-heap vs. max-heap, and the negation trick

Most standard libraries only give you a min-heap out of the box (Python's heapq, for instance, has no built-in max-heap). To simulate a max-heap, negate values on the way in and negate again on the way out:

For tuples, negate only the field you're prioritizing by — the tiebreaker fields keep their natural order (or negate those too, if you want reversed tiebreaking):

Java and C++ go the other way: java.util.PriorityQueue is min-heap by default (pass Comparator.reverseOrder() for a max-heap), while C++'s std::priority_queue is max-heap by default (pass std::greater<T> as the third template argument for a min-heap). Mixing this up when switching languages mid-prep is one of the most common silent bugs — always state out loud which behavior you're assuming before you code.

The top-K pattern

The pattern that shows up constantly: "find the K largest/smallest/closest/most-frequent elements." The naive approach — sort everything, take the first K — costs O(n log n). A heap gets you to O(n log k), which matters a lot when k << n.

The counterintuitive part: to find the K largest elements, you maintain a min-heap of size K, not a max-heap.

• Push each element onto the heap.
• Whenever the heap's size exceeds K, pop the minimum.
• After processing everything, the heap holds exactly the K largest elements, and its root — the smallest of the K largest — is the Kth largest element overall.

Why a min-heap for a "largest" query? Because you need fast access to the weakest member currently admitted so you can decide whether to evict it — that's the smallest element of your current top-K set, which is exactly what a min-heap gives you at its root. (Symmetrically, use a max-heap of size K to track the K smallest elements.) heapq.heapreplace(heap, x) is a useful micro-optimization here: it pops-then-pushes in a single O(log k) operation instead of two.

Why O(n log k) beats O(n log n)

You touch every one of the n elements once, and each heap operation costs O(log k) because the heap never grows past size K. When K is small relative to n (e.g., "top 10 out of a million"), this is a dramatic win over sorting the entire input. If K is close to n, the two approaches converge, and simplicity may favor just sorting.

A related but different heap pattern: repeatedly merge the two smallest

Top-K maintains a heap of a fixed size and evicts the weakest member as new elements arrive. A different, equally common heap pattern shows up when you need to repeatedly combine the two currently smallest elements in the whole structure, growing a merged result until only one item remains — pop two, combine them, push the result back, repeat. Last Stone Weight (below) is the simplest version of this shape. The Greedy topic's Huffman Coding & Optimal Caching subtopic builds an entire optimal-compression algorithm out of exactly this pattern (repeatedly merge the two least-frequent symbols), and frames it explicitly as "a heap-driven greedy, not a sort-driven one" — worth a look once this topic feels solid, since it's the same core heap operation applied to a genuinely different problem shape than top-K.

An alternative to the heap: Quickselect (expected O(n))

For a single "find the Kth largest/smallest element" query (as opposed to "give me all K of them, or keep a running top-K as a stream arrives"), there's a technique that beats even the heap's O(n log k): quickselect, which runs in expected O(n) time and O(1) extra space. It's the single most common follow-up to "Kth Largest Element in an Array" — after you present the heap solution, expect "can you do better than O(n log k)?"

Quickselect reuses quicksort's partition step, but throws away the half of the array it doesn't need instead of recursing into both halves:

1. Pick a pivot and partition the array so everything < pivot ends up to its left and everything > pivot ends up to its right — exactly like quicksort's partition step. After partitioning, the pivot sits at its final sorted position, call it index p.
2. Compare p to the target rank k:
   • If p == k, the pivot is the answer — stop.
   • If p > k, the answer is in the left partition — recurse only into arr[:p].
   • If p < k, the answer is in the right partition — recurse only into arr[p+1:].

Why this is expected O(n), not O(n log n)

Unlike quicksort — which recurses into both partitions and does O(n log n) work overall — quickselect only ever recurses into the one partition that contains the target rank, and throws the other one away entirely. That gives a recurrence of roughly T(n) = T(n/2) + O(n) (partition cost at each level), which by the same geometric-series reasoning as heap-building sums to O(n) overall, not O(n log n). This is the same category of surprising-but-provable result as the O(n) heapify fact above — both come from "the work shrinks fast enough each level that the total is dominated by the first level," not from a full binary-tree's worth of levels each doing full work.

Why "expected," not worst case: a poorly chosen pivot (e.g., always picking the first element on an already-sorted or adversarial input) can degrade this to O(n²), identical to quicksort's worst case. A random pivot makes that degradation astronomically unlikely rather than impossible — for interview purposes, "expected O(n) with a random pivot" is the correct and complete claim; don't overclaim worst-case O(n) unless you're using the more involved median-of-medians pivot selection (rarely expected in an interview, worth knowing the name exists but not worth memorizing the implementation).

Heap vs. quickselect — when to reach for which

	Min-heap of size k	Quickselect
Time	O(n log k)	O(n) expected, O(n²) worst case
Space	O(k)	O(1) extra (in-place partitioning)
Good for	Streaming data, or when you need all K elements, not just the boundary one	A single one-shot query on a static array in memory
Mutates input?	No	Yes (partitions the array in place)

If the interviewer's problem is phrased as a stream ("process numbers as they arrive, keep track of the Kth largest so far"), the heap is the only viable option — quickselect requires the whole array up front to partition against. If it's a one-shot query on a fixed array and average-case performance is acceptable, quickselect is the more impressive, lower-overhead answer. Being able to produce both, and to correctly say which situation calls for which, is exactly the kind of range a Senior-level interviewer is probing for.

Heap vs. sorted array vs. BST for priority-queue operations

Structure	Find min/max	Insert	Delete min/max	Build from n items
Unsorted array	O(n)	O(1)	O(n)	O(n)
Sorted array	O(1)	O(n)	O(n) shift	O(n log n)
Binary heap	O(1)	O(log n)	O(log n)	O(n)
Balanced BST (e.g. Java TreeMap)	O(log n)	O(log n)	O(log n)	O(n log n)

A heap wins whenever you only need the extreme element, not arbitrary rank queries or in-order traversal. If you need "find the 5th smallest at any moment" or range queries, reach for a balanced BST or sorted structure instead — a heap can't answer those efficiently since it only guarantees order along root-to-leaf paths, not between siblings.

Pitfalls and interview gotchas

• Comparator/tuple ordering on compound objects. When you push tuples like (priority, item), Python's heapq compares element-by-element, so if two priorities tie, it falls through to comparing item. If item isn't comparable (e.g., a custom object or a dict), this throws a TypeError at runtime — add an explicit tiebreaker field (like an insertion counter) to avoid it.
• Forgetting the heap is not fully sorted. heap[1] is not guaranteed to be the second-smallest element — only heap[0] has a guaranteed rank. Don't index into a heap's backing array expecting sorted order.
• Ties in top-K problems. If the problem says "return any valid answer" for ties, don't over-engineer a tiebreak; if it specifies one (e.g., "smaller index first"), bake it into the tuple you push.
• Heapify vs. repeated push. Building from a known list with heapq.heapify(arr) is O(n); pushing the same elements one at a time into an empty heap is O(n log n). Prefer heapify when you have all the data up front.
• Stability isn't guaranteed. Heaps don't preserve insertion order among equal elements the way a stable sort would — don't rely on it.

How to state this in an interview

"I'll maintain a min-heap of size k. Each of the n elements is pushed and possibly popped once, and each heap operation is O(log k), so this runs in O(n log k) time and O(k) space — better than the O(n log n) sort-everything approach since k is much smaller than n here."