Heap, sort or quickselect?

Heaps and priority queues Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

A service receives events all day and must always show the 10 largest so far. What fits best?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A A min-heap of size 10

Right: each event costs O(log 10), and the ten largest are always in the heap.

Streaming input with a small k is the case where a bounded heap clearly wins.

Why not the others?
  • B Sort all events after each arrival. Cost grows with every event.
  • C Quickselect after each arrival. It reprocesses all n events each time.

30-second answer

Sort when you need everything in order once: O(n log n), simple. Use a heap when items keep arriving or you only need the top k: O(n log k), and it works on streams. Use quickselect for one k-th value in a fixed in-memory list: O(n) on average but O(n²) worst case. Job schedulers use heaps because new jobs keep arriving and only the next one matters.

Practise saying it · 45 s. No recording, just a timer

Compare heap, sort and quickselect.

Say your answer out loud, then check which of these points you covered:

  • Sort: all in order once
  • Heap: stream or top k
  • Quickselect: one k-th, average O(n)

Deep dive

For tiny n, sorting is often fastest in practice.

A heap of size k uses O(k) memory; sorting a copy uses O(n).

Timer and job queues are heaps keyed by the next run time.

Common mistakes

  • Sorting a stream again after every new item.
  • Calling quickselect O(n) without mentioning its worst case.

Senior take & follow-ups

Choose out loud and name the deciding factor: streaming, k much smaller than n, or one-off order.

Follow-up questions

Think of your answer first, then open the hint.

  1. What does a job scheduler keep in its heap?

    Show hint

    (next run time, job id) pairs; it sleeps until the top's time.

  2. How do you get the top k in sorted order?

    Show hint

    Pop the size-k heap and reverse, or sort the k survivors.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.