LESSON 11 · PATTERN GUIDE

Heap / Top K

Use a heap to repeatedly access the smallest or largest candidate without fully sorting everything.

FIRST, LEARN THE PATTERNA priority queue keeps one extreme at its root. A size-k heap can keep only the k best items seen so far.

The task asks for the kth largest value, most frequent items, or repeatedly selecting the next best candidate.

How to approach it

Choose a min-heap or max-heap based on what should be removed first; for top k, keep heap size bounded by k when appropriate.

Watch out for

Tie-breaking may matter, and a heap does not provide full sorted order for all elements.

A CLOSER EXPLANATION

A heap keeps its smallest or largest element readily available while partially ordering the rest. If only k winners are needed, keep a heap of size k and evict the weakest candidate whenever it grows too large. This can be cheaper than sorting all n items, especially when k is small.

NOW YOU TRY

Practice question

What is the third-largest value in [7, 2, 9, 4, 1]?

EXAMPLEvalues = [7, 2, 9, 4, 1], k = 3Give your answer before revealing the explanation.

Show a hint

The values in descending order begin 9, 7, 4.

Show an answer

CONNECT IT TO REAL LIFE

Heap / Top K at work

A support dashboard shows unresolved tickets with priorities [2, 9, 4, 7, 5]. Which three should appear in the highest-priority queue?

Show one possible approach

Priorities 9, 7, and 5. A size-3 min-heap can retain the three largest values while tickets are scanned.

Practice next

Use these problem IDs to find additional practice for this pattern:

2153476927039731046