← Learn DSA · Lesson 6 of 9
Heaps & Priority Queues
Keep the best element to hand without sorting everything.
The idea
A heap keeps the smallest — or largest — element instantly available while leaving everything else only loosely ordered. That partial order is the point: full sorting is O(n log n), and most problems never need it.
The operations are peek in O(1), and push and pop in O(log k) for a heap of size
k. It is usually stored as an array, with a node's children at 2i+1 and 2i+2,
so there are no pointers and no allocation per node.
The pattern that shows up constantly is top-k: keep a heap of size k while streaming through n elements. For the k largest, use a min-heap — the smallest of your current best sits on top, ready to be evicted the moment something better arrives. That is O(n log k), which beats sorting when k is much smaller than n, and needs O(k) memory rather than O(n).
The same structure is a priority queue, which is what makes Dijkstra's algorithm work: always expand the nearest unvisited node.
Walkthrough
A heap is an array. Sift-down repeatedly swaps a node with its larger child — watch the bar sink to its level.
What it costs
- time
- O(log k) push and pop, O(1) peek
- space
- O(k)
Top-k in O(n log k) rather than O(n log n). When k is 10 and n is ten million, that difference is the whole solution.
When to reach for it
- You need the best element repeatedly, and do not care about the order of the rest.
- Top-k, k-th largest, or a running median.
- Data arrives as a stream and cannot all be held at once.
- You are always expanding the cheapest option next — Dijkstra, A*, scheduling.
Rather than the obvious alternative
Sorting
Sorting is O(n log n) and gives you every position. For top-k a heap is O(n log k), which for k=10 and n=10 million is the whole solution.
A sorted array
O(1) access to the best, but O(n) insertion. The heap trades slightly slower access for O(log n) insertion, which wins the moment the data changes.
A balanced BST
It can do everything a heap can and more, at a higher constant factor and much more code. Use it only when you also need ordered iteration or arbitrary deletion.
How to spot it
- The problem says 'k largest', 'k smallest', 'k most frequent', or 'median'.
- You need repeated access to the current best without caring about the rest.
- Data arrives as a stream and cannot all be held at once.
- You are always expanding the cheapest option next — Dijkstra, A*, scheduling.
Where it goes wrong
The wrong heap direction
For the k *largest*, you want a *min*-heap. It feels backwards; the top is the weakest of the ones you are keeping, which is exactly what you want to evict.
Sorting when a heap would do
Sorting to take the top 5 is correct and wasteful. Fine at small n, the wrong answer in an interview.
Expecting sorted output
A heap is not sorted. Only the root is guaranteed — reading the underlying array gives you nothing meaningful.
Practise it
- Kth Largest Elementmedium
- Top K Frequent Elementsmedium
Build it
The problems above are one function each. These assemble the same ideas into a working thing across several files.