juniorHeaps and Maps

When would you use a min-heap over a max-heap?

Updated Feb 20, 2026

Short answer

Use a min-heap when the smallest element is what you repeatedly need — Dijkstra's next-closest vertex, the earliest-deadline job, a merge of sorted streams. Use a max-heap for the largest. The counter-intuitive case is top-K: to find the K largest items you use a min-heap of size K, because you need cheap access to the smallest of your current best to decide what to evict.

Deep explanation

The rule is that the heap's root should be the element you want to inspect or discard next.

Min-heap fits naturally when:

  • Dijkstra and A* — repeatedly take the unvisited vertex with the smallest tentative distance.
  • Event simulation and schedulers — process the earliest timestamp next.
  • Huffman coding — repeatedly merge the two lowest-frequency nodes.
  • Merging K sorted lists — the next output element is the smallest head.

The top-K inversion is the one worth internalising. To keep the K largest of a stream, maintain a min-heap of size K:

Python
import heapq


def top_k(stream, k):
    heap = []                          # MIN-heap, holds the k largest so far
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:              # bigger than our smallest keeper
            heapq.heappushpop(heap, x) # evict the smallest, insert x
    return sorted(heap, reverse=True)

The root is the weakest of the current champions, which is exactly the element to compare against and evict. A max-heap would put the strongest at the root — the one you never want to remove — leaving no cheap way to find the weakest.

This costs O(n log k) time and O(k) space, versus O(n log n) and O(n) for sorting everything. When k is small and n is huge, that is the difference between feasible and not — and it works on a stream you cannot hold in memory.

Real-world example

Ten million search queries, and you want the 100 most frequent — with only enough memory for a few hundred entries.

Python
heap = []                                   # min-heap of (count, query)
for query, count in counts.items():         # 10,000,000 entries
    if len(heap) < 100:
        heapq.heappush(heap, (count, query))
    elif count > heap[0][0]:                # beats the weakest of our top 100
        heapq.heapreplace(heap, (count, query))

Peak memory is 100 tuples. Sorting all ten million to take the head would need every record resident and O(n log n) time.

Common mistakes

  • - Reaching for a max-heap for top-K. You need the smallest of the kept set to know what to evict, so a min-heap of size K is correct.
  • - Sorting the whole dataset for a small K, paying O(n log n) and full memory where O(n log k) and O(k) would do.
  • - Forgetting to bound the heap at size K, so it grows to n and the memory advantage disappears.
  • - Using `heappush` followed by `heappop` instead of `heappushpop`/`heapreplace`, which does the same work in one sift rather than two.
  • - Assuming the final heap is sorted — it must be sorted explicitly before returning ordered results.

Follow-up questions

  • Why does top-K use a min-heap rather than a max-heap?
  • What is the complexity of top-K with a heap versus sorting?
  • When is quickselect better than a heap for top-K?
  • How would you build a double-ended priority queue?

More Heaps and Maps interview questions

View all →