When should you use a heap instead of sorting?

Use a heap instead of sorting when you want the k smallest or largest out of n and k is much smaller than n, when the data arrives as a stream and you need answers before it ends, or when you repeatedly extract the current minimum while inserting new items. Sorting is the right tool when you need the whole order, or when you will query the sorted result many times. The crossover is about cost per answer.

The clean way to see the trade-off is to ask what each structure promises. A sorted array promises the entire order at once, for n log n comparisons paid up front, after which any positional question is free. A heap promises only the smallest element, but promises it continuously: log n to insert, log n to remove the minimum, and the structure stays valid as items come and go. Everything below is a consequence of that difference, and most misuse comes from paying for the whole order when a single edge of it was wanted.

Why is a heap cheaper for the top k?

Because it never orders the elements it discards. To find the k largest of n items, keep a min-heap of size k: push each item, and whenever the heap exceeds k, pop the smallest. Each of the n items costs at most log k, so the total is n log k. Sorting costs n log n and then reads k values off the end. When k is 10 and n is ten million, log k is about 3 and log n is about 23: the heap does roughly an eighth of the comparisons, and it does them in a structure of ten elements that lives in a single cache line, while the sort shuffles the whole ten-million-element array.

The heap-as-array layout is what makes the constant factor small as well as the asymptotic one: parent and children are found by index arithmetic, no pointers, and the heap as array deep-dive shows why a sift-down of depth log k touches so little memory. The walkthrough for kth largest element applies exactly this and compares it to the alternatives.

When does sorting win anyway?

When k approaches n, when the data is static and queried repeatedly, or when the data is small. If you need the top half of the elements, n log k is nearly n log n and the heap's overhead per operation, with its sift-ups and sift-downs, loses to a well-tuned sort with its sequential memory access. If you will ask "what is the 100th largest" a thousand times on the same data, sort once and index; a heap answers only one such question per pop. And below a few thousand elements, the sort's tighter inner loop beats the heap's logic regardless of what the complexity says. Measure at your actual n before assuming the heap is faster.

There is a third contender for one-shot selection. Quickselect finds the kth element in expected linear time, better than either n log k or n log n, by partitioning like quicksort but recursing into only one side. It needs the whole array in memory and gives no ordering among the top k. The quickselect deep-dive shows when that linear bound is worth its lack of structure; the short version is: static data, one query, k not tiny, choose quickselect.

What does a stream change?

Everything, because sorting needs the end of the input and a stream has no end. A heap maintains the top k of everything seen so far, updated in log k per arrival, and can report at any moment. Running medians, sliding-window maxima, the ten most frequent items in the last hour: these are heap problems because they are online problems. The top k frequent elements walkthrough is the canonical example, combining a frequency count with a size-k heap so that the answer is available without a final sort.

Streams also make memory the binding constraint. A size-k heap uses k slots regardless of how many items pass through it; a sort needs all n. When n does not fit, the heap is not merely faster, it is the only option short of external sorting.

What about repeated insert and extract-min?

This is the case where a sorted array is not even in the running. A scheduler that holds pending tasks and always runs the earliest deadline, Dijkstra's algorithm holding tentative distances, an event simulation pulling the next event: each interleaves inserts with extract-min indefinitely. A sorted array makes insertion O(n) to shift elements; a heap makes both operations O(log n). Reasoning through Dijkstra makes the total concrete: with E edges and V vertices, each edge may cause one decrease or insert and each vertex is extracted once, so the heap version runs in (E plus V) log V, where a sorted-array version would spend V squared on extractions alone. The Dijkstra invariant deep-dive is built on this structure.

How do the options compare?

Need	Sort	Heap	Quickselect	Choose
Full order, queried many times	n log n once	n log n via repeated pops, no random access	Not applicable	Sort
Top k of static data, k small	n log n	n log k	n expected, unordered	Heap or quickselect
Top k of a stream	Impossible until end	log k per item, k memory	Needs all data	Heap
Interleaved insert and extract-min	n per insert	log n each	Not applicable	Heap
Anything under a few thousand items	Fast, simple	Overhead dominates	Overhead dominates	Sort

A note on the common interview trap hidden in that table. Asked for the top k, many candidates sort the whole array, and the interviewer's follow-up is always the same: what if the array does not fit in memory, or what if k is 3 and n is a billion? Having the size-k heap ready as the second answer, with the n log k count stated aloud, is worth more than getting the sort right quickly. The sorting module covers when a full sort is the honest answer and when it is the lazy one.

Read the table by asking two questions of your problem: is the input finished, and how much of the order do I need? Finished and all of it: sort. Finished and an edge of it: heap or quickselect, by whether you need the edge ordered. Unfinished: heap. Small: sort, and stop optimising.

Frequently asked questions

Is building a heap O(n log n)?

Not if you build it bottom-up. Inserting n items one at a time costs n log n, but heapifying an existing array by sifting down from the middle costs O(n): most nodes sit near the bottom and sift only a level or two. That makes "heapify then pop k" cost n plus k log n, another point in the heap's favour for small k.

Should I use a heap for a running median?

Yes, two of them: a max-heap for the lower half and a min-heap for the upper half, kept balanced in size so the median is at one or both tops. Each arrival costs log n and the median is always available. A sorted structure would cost linear time per insertion.

Is a balanced tree ever better than a heap?

When you need more than the minimum: predecessor and successor queries, deletion of arbitrary elements by key, or ordered iteration. A heap only knows its top. A balanced tree does all of those in log n at the cost of pointers, a larger constant, and more code.

To see the top-k pattern implemented and compared against sorting and quickselect with the counts written out, work through kth largest element, then the streaming version in top k frequent elements.