Pattern 9 of 18 · Core Structures

Heap / Priority Queue

Always grab the min or max in O(log n) — essential for top-k and scheduling problems.

A heap keeps the minimum (or maximum) element accessible in O(1), with O(log n) insert and remove. It's the tool whenever you repeatedly need "the smallest/largest remaining item" without needing everything fully sorted.

Key concepts

  • Min-heap: the root is always the smallest element. Max-heap: the root is always the largest.
  • Insert and extract-min/max both run in O(log n); peeking at the top is O(1).
  • Two heaps (one min, one max) can track a running median by keeping the two halves balanced.

When to use it

  • You need the top-k largest/smallest elements, not a full sort.
  • You're merging multiple sorted sequences (always take the smallest available head).
  • You need a running min/max/median as data streams in.

Tips

  • "Top k" or "k closest" in a problem statement is almost always a heap of size k.
  • A heap saves you from re-sorting after every update — that's its whole value over just using a sorted array.
  • For the median of a stream, keep a max-heap for the lower half and a min-heap for the upper half.

Practice problems (7)

Blind 75 (1):

More from Blind 150 (6):

← TriesBacktracking →

See the full roadmap →