Heaps & Top-K

Review boundary and corrected contracts

heapq offers max-heap APIs starting in Python 3.14; negation is the portable numeric technique used here. A generic payload needs a numeric tiebreaker when priorities tie. Top-k uses O(n log(k+1)) heap work; a frequency map is not O(k) total space.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for heaps & top-k is in the 6-month plan: S029 — theory.

Learning objective: Reach for a heap the instant a problem says 'top K', 'K smallest', or 'K most frequent', and know why a size-K heap beats a full sort.

Series: LeetCode — From Basics to Production-Ready · Session 26 / 65 · Phase 1 · Core patterns

Prerequisites. Arrays, collections.Counter, and tuple comparison in Python. This lesson uses portable numeric min-heap operations; public max-heap operations are also available starting in Python 3.14. Unless noted, 1 <= k <= n for selecting items, or 1 <= k <= m for m distinct frequency keys. These functions assume valid k rather than validate it.

Watch first

Optional original references: kth largest, top-k frequencies, and binary heaps. They supplement, rather than replace, the worked code below.

Why this session exists

Top-K suggests a bounded heap, especially for a stream or small k. Sorting is also correct and often simplest when full order is useful or k is close to n; the choice is a workload decision, not a correctness test.

A heap exposes its extreme in O(1) and inserts or removes in O(log n) for a heap of n elements. A bounded heap selects k items in O(n log(k+1)) time without ordering all n; its returned list is in heap order, not sorted rank order. Sorting just the k survivors would add O(k log(k+1)). The +1 keeps the bound meaningful at k = 1.

The portable heappush and heappop operations implement a min-heap. For numeric max-heap behavior across Python versions, negate on insertion and removal. Python 3.14 additionally provides heappush_max and heappop_max; do not mix min-heap and max-heap conventions in the same list.

Blank-file warm-up

Five minutes, empty file, no notes. Reproduce the heapq idioms and the size-K invariant:

import heapq
 
# min-heap (portable API; Python 3.14 also has max-heap APIs)
x = 7
h = []
heapq.heappush(h, x)
peek = h[0]                         # inspect BEFORE removing the only item
smallest = heapq.heappop(h)          # h is now empty
 
# separate numeric max-heap: negate going in and coming out
max_h = []
heapq.heappush(max_h, -x)
largest = -heapq.heappop(max_h)
 
# heapify an existing list in O(n); mutates nums
nums = [3, 1, 2]
heapq.heapify(nums)
 
# K LARGEST -> keep a MIN-heap of size k.
# The root is the smallest of your current top-k; if a new value beats it, swap.
def k_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)         # evict the smallest -> h holds the k largest
    return h                          # h[0] is the k-th largest

If you cannot type the size-K eviction loop without thinking, that is today's finding. The counter-intuitive part — that you keep a min-heap to find the largest — is exactly the part to over-learn.

Pattern anatomy

The shape: you have n items, you want the K best of them by some key, and K is meaningfully smaller than n.

The invariant: after t inputs, the heap holds the best min(k, t) items seen so far. Once full, its root is the weakest survivor. A strictly better item can replace that root; an equal-priority item is interchangeable when the problem permits any tie choice. The shown push-then-pop loop temporarily holds k+1 items and restores the invariant after eviction.

The direction flip is the thing to internalise: to keep the K largest, use a min-heap, because you want fast access to the weakest survivor so you can evict it. To keep the K smallest, use a max-heap (negate).

# generic top-k by a key, min-heap of (key, unique sequence, item)
def top_k(items, k, key):
    h = []
    for sequence, it in enumerate(items):
        heapq.heappush(h, (key(it), sequence, it))
        if len(h) > k:
            heapq.heappop(h)
    return [it for _, _, it in h]

The unique sequence prevents comparison of payload objects. For equal keys this particular eviction loop favors later arrivals, because earlier sequence numbers are smaller and get popped first; it is not a stable first-arrival top-k. Output order is unspecified.

The cue

You should hear "heap" from these tells in the problem statement:

1. The literal words "K largest / K smallest / K closest / K most frequent." The most direct cue in all of algorithms. Almost always a heap unless K equals n.
2. "Top K" or "the K best by some score." Same pattern with a key function.
3. A stream you cannot fully sort — elements arrive one at a time and you must maintain a running top-K without storing and re-sorting everything.
4. "Merge K sorted lists/arrays" — a min-heap of the K current heads pulls the global minimum in O(log(k+1)) per pop/push step.
5. "Median of a stream" — the two-heap variant (you will meet this again in L52). If you see running median, think heaps, not sorting.

Guided solve

Kth Largest Element in an Array. Return the k-th largest element (in sorted order, not distinct).

Narrate it: the k-th largest is exactly the smallest element of the top-K set. So keep a min-heap of size K; after processing every element, its root is the answer.

def findKthLargest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]          # smallest of the k largest == k-th largest overall

O(n log(k+1)) time, O(k) space. The instinct to sort and index nums[-k] also works at O(n log n) — say so, then explain why the heap is better when k is small. (A quickselect solution reaches O(n) average and is worth mentioning as the "if they push on complexity" answer.)

Top K Frequent Elements, end to end. Given nums and k, return the k most frequent values.

Brute force: count, then sort the counts descending, then slice — O(n + m log m) where m is the number of distinct values. Correct, and a reviewer will immediately say "better than O(n log n), please."

The pattern insight: you do not need the distinct values ordered, only the top k of them, so cap a min-heap at k keyed on count.

from collections import Counter
import heapq
 
def topKFrequent(nums, k):
    counts = Counter(nums)              # O(n), m distinct keys
    h = []                              # min-heap of (count, value), capped at k
    for value, c in counts.items():
        heapq.heappush(h, (c, value))   # tuples compare on count first
        if len(h) > k:
            heapq.heappop(h)            # evict the least frequent survivor
    return [value for _, value in h]    # order within the answer is unspecified

O(n + m log(k+1)) time, O(m) space for the counter plus O(k) for the heap. Values are integers here so tuple comparison never falls through to a non-comparable payload — but if the payload were a list or a tree node you would push (c, i, payload) with a running i.

The follow-up they escalate to: "make it strictly better than O(n log n) even when k is close to m." Bucket sort answers it. Counts are bounded by n, so index an array of length n+1 by count and walk it downwards:

def topKFrequent_buckets(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]   # index = frequency
    for value, c in counts.items():
        buckets[c].append(value)
    out = []
    for c in range(len(buckets) - 1, 0, -1):       # walk high frequency first
        for value in buckets[c]:
            out.append(value)
            if len(out) == k:
                return out
    return out

O(n) time and O(n) space. This only works because counts are bounded by n — name that precondition out loud, because it is the thing that makes the trick legal.

Solo timed

Fifteen minutes each, timer visible. Hints only — no solutions.

• Top K Frequent Elements — count with a Counter first, then run the size-K heap on (count, value) pairs. heapq.nlargest(k, counter, key=counter.get) is the one-liner, but implement the heap yourself at least once.
• Merge k Sorted Lists — push the head of each list as (value, list_index, node) (the index breaks ties so nodes never get compared). Pop the min, push its successor. O(N log(k+1)).
• K Pairs with Smallest Sums — a min-heap seeded with the first column; each pop lazily pushes its right neighbour. Do not generate all pairs.

Common failure modes

1. Using a max-heap for K-largest. The classic inversion error. K-largest wants a min-heap so the root is the evictable weakest. Wire it backwards and you evict your best elements.
2. Mixing heap conventions. Portable heappop removes the minimum; negation simulates a numeric maximum. Python 3.14+ also has public max-heap APIs, which require their corresponding invariant.
3. Comparing un-comparable payloads. Pushing (count, node) where two counts tie makes Python compare the nodes and crash. Insert a unique tiebreaker index: (count, i, node).
4. Ignoring the workload. sorted(nums)[-k] is correct. Compare its O(n log n) work with the bounded heap's O(n log(k+1)); sorting can be preferable when full order is needed or k is large.

Myth: To find the K largest elements you keep the K largest in a max-heap.

Why: It feels natural because 'largest' pairs with 'max-heap' in your head, but it is exactly backwards. With a max-heap of size K, the root is the biggest of your set — which is the element you least want to remove. You need fast access to the smallest of your current top-K so you can evict it when something better arrives. That is a min-heap. Say it out loud until it stops feeling wrong: K-largest uses a min-heap, K-smallest uses a max-heap.

Steps 1: You want the K best of n items, and K is much smaller than n.

Steps 2: A full sort orders all n items, which is n log n work to answer a question that only concerns K of them.

Steps 3: A binary heap gives O(log m) insert and O(log m) extract-extreme on a set of size m, without ordering the rest.

Steps 4: After each eviction the heap has at most k items; a push can temporarily create k+1. Each iteration costs O(log(k+1)), for O(n log(k+1)) total.

Steps 5: The root of that capped heap is the weakest survivor, so a new item is admissible if and only if it beats the root — one O(1) comparison decides discard-or-swap.

Steps 6: Testable prediction: for K = 1 the size-K heap degenerates to a single running max/min in O(n), which is exactly what you would write by hand for 'find the maximum' — if your general code does not reduce to that for K=1, your eviction condition is wrong.

Picture: A velvet rope outside an exclusive club with exactly K spots inside. The bouncer stands at the door watching the least impressive person currently inside. Each newcomer is compared only against that weakest insider: better, and the weakest is thrown out to make room; worse, and the newcomer never gets past the rope. After each admission decision the club has at most K members; the push-then-pop implementation temporarily stages one extra candidate before eviction.

Trigger: Fires whenever a problem wants the K best of a large or streaming collection — 'K largest', 'top K', 'K closest', 'K most frequent', or 'merge K sorted things'.

Name: Size-K heap

Gain: O(n log(k+1)) time, O(k) space; works on an unbounded stream; naturally maintains a running top-K.

Cost: The min-for-largest inversion is easy to get wrong; payloads need a tiebreaker to stay comparable.

Name: Sort then slice

Gain: Trivial to write and impossible to get subtly wrong; fine when n is small or you need the full order anyway.

Cost: O(n log n) time and O(n) space; cannot run on a stream; does redundant work when K is small.

Pick: Reach for the heap whenever K is meaningfully smaller than n or the input is a stream; sort-and-slice only when n is small, you already need everything ordered, or clarity matters more than the constant factor.

Memory hook — "opposite heap, weakest root"

The one thing that goes wrong under pressure is the direction flip, so peg it with a three-word phrase: opposite heap, weakest root.

• Opposite heap — the heap type is always the opposite of the word in the problem. "K largest" takes a min-heap; "K smallest" takes a max-heap. Whenever you write heapq and the problem said largest, your fingers should feel the mismatch and that mismatch is correct.
• Weakest root — the root of the capped heap is always the weakest member of your current winners, which is simultaneously the eviction target and, when the loop ends, the answer to "what is the K-th best".

The shape-of-the-code peg is four lines and never varies: push, check size, pop if over, done. If your loop has an if x > h[0] guard instead, that is a valid micro-optimisation but the same four beats.

For portable numeric max-heap behavior, negate on insertion and negate again on removal. Do not negate a bounded min-heap used to keep the K largest. Python 3.14 also supplies public max-heap operations, so heapq is no longer min-only.

What reviewers actually ask

Top-K offers a useful comparison between correct approaches: sorting, bounded heaps, selection, and frequency buckets. Streaming adds a different constraint from a finite offline array.

• 215 · Kth Largest Element in an Array (Medium) — Practice selection. Probing whether you reach past sorting. Follow-up: "can you do better than O(n log(k+1))?" — quickselect, O(n) average.
• 347 · Top K Frequent Elements (Medium) — Practice selection. Probing the count-then-heap composition. Follow-up: "your algorithm must be better than O(n log n)" — bucket sort by frequency gives O(n).
• 23 · Merge k Sorted Lists (Hard) — Practice selection. Probing the k-way merge and, critically, the tiebreaker index. Follow-up: compare against divide-and-conquer pairwise merging, which hits the same bound without a heap.
• 295 · Find Median from Data Stream (Hard) — Practice selection. Probing the two-heap balance invariant. Follow-up: "what if all numbers are in the range 0 to 100?" — a counting array beats both heaps.
• 973 · K Closest Points to Origin (Medium) — Practice selection. Probing top-K with a computed key. Follow-up: "why can you skip the square root?" — squared distance preserves ordering.
• 703 · Kth Largest Element in a Stream (Easy) — Practice selection. Probing the streaming form where the heap is class state, not a local.
• 621 · Task Scheduler (Medium) — Practice selection. Probing a max-heap driving a greedy schedule rather than answering a top-K question directly.

For streaming kth-largest values, the heap keeps O(k) state over each finite prefix. Exact top-k frequencies are different: the Counter grows with the number of distinct keys, and a changing count may change priority. The batch frequency loop above is not an O(k)-memory exact algorithm for an unbounded-vocabulary stream.

Complexity

The size-k heap takes O(n log(k+1)) time and O(k) space for valid positive k. A push temporarily reaches k+1, then eviction restores size k. Frequency selection additionally stores O(m) counts and costs O(n + m log(k+1)); buckets cost O(n) time and space. Merge-k lists costs O(k + N log(k+1)), including scanning the k input heads; N is the total node count.

You can now…

• Fire 'heap' automatically on the phrases K largest, K smallest, K closest, K most frequent, and merge K sorted.

• State and defend the inversion: K-largest uses a min-heap, K-smallest uses a max-heap.

• Write the four-beat size-K loop — push, check size, pop if over, done — without notes.

• Use numeric negation for portable max-heap behavior, or the public max-heap APIs added in Python 3.14.

• Add a unique tiebreaker index so non-comparable payloads never reach a comparison.

• Justify O(n log(k+1)) against sort-and-slice's O(n log n), and name quickselect as the O(n)-average alternative.

• Explain why a single heap cannot track a running median and what the two-heap fix is.

Quiz

Self-check (answer follows each question).

Q: To keep the K largest elements, which kind of heap do you use, and what does its root represent?

A: A min-heap. Its root is the smallest of the current top-K — the weakest survivor and therefore the one to evict when a stronger candidate arrives.

Q: Why is O(n log(k+1)) an improvement over sorting when K is small?

A: Sorting orders all n elements (n log n work) to answer a question about only K of them. The capped heap costs O(log(k+1)) per element, which is constant at k = 1. When k is small this can save asymptotic work; it does not prove a measured speedup for every input.

Q: How do you get numeric max-heap behavior portably, and what did Python 3.14 add?

A: Negate on push and pop with the min-heap API: heappush(h, -x); largest = -heappop(h). Python 3.14 also added public heapify_max, heappush_max, and heappop_max operations.

Q: When merging K sorted lists, why push (value, index, node) rather than (value, node)?

A: Without a tiebreaker, equal values make Python compare node objects, which lack ordering. A list index suffices only while at most one pending node from each list is in the heap: pop its current head before pushing its successor. A general priority queue needs a unique insertion counter.

Q: What is the admission test for a new element against a full size-K heap?

A: Compare it to the root (the weakest survivor). If it beats the root, evict the root and insert; otherwise discard it — it cannot be in the top K.

Q: Stretch: how would you find the running median of a stream, and why can't a single heap do it?

A: Keep a max-heap for the lower half and a min-heap for the upper half. Every lower value must be no larger than every upper value, and sizes differ by at most one. For an odd prefix use the larger heap's root; for an even prefix average both roots. A single ordinary heap exposes only an extreme, not the middle in O(1). Exact two-heap median storage grows with the stream prefix.

Practice queue

Grind these in order, easy to hard. The two marked as anchors are the ones the rest reduce to — schedule them for spaced repeat.

1. 703 · Kth Largest Element in a Stream — Easy. The size-K loop as persistent class state.
2. 1046 · Last Stone Weight — Easy. Max-heap by negation, nothing else.
3. 215 · Kth Largest Element in an Array — Medium. Anchor, +7d then +21d.
4. 973 · K Closest Points to Origin — Medium. Top-K on a computed key.
5. 347 · Top K Frequent Elements — Medium. Anchor, +7d then +21d. Solve it both ways.
6. 621 · Task Scheduler — Medium. Max-heap driving a greedy schedule.
7. 373 · K Pairs with Smallest Sums — Medium. Lazy expansion — never materialise all pairs.
8. 23 · Merge k Sorted Lists — Hard. The tiebreaker index lives or dies here.
9. 295 · Find Median from Data Stream — Hard. Two heaps; returns properly in L52.

Spaced queue

Re-solve whatever is due from earlier sessions before you close. Status ladder for everything you touched today:

• Cold — unaided, under 15 minutes, optimal → returns in 60 days
• Warm — unaided but slow or suboptimal → returns in 21 days
• Hint — needed a nudge or a peek → returns in 7 days
• Failed — read the editorial → returns in 2 days, then 7

Kth Largest and Top K Frequent are the two to over-learn; they are the base cases the rest of the family reduces to.

• 'Top K / K largest / K smallest / K most frequent' → heap, almost always.

• K-largest uses a MIN-heap of size K; K-smallest uses a MAX-heap. The inversion is the whole trick.

• The root of a full size-K heap is the weakest survivor — the eviction target and the answer to 'the K-th largest'.

• O(n log(k+1)) beats sort-and-slice's O(n log n) whenever K is meaningfully smaller than n, and unlike sorting it works on a stream.

• Portable numeric max-heaps can use negation; Python 3.14 adds public max-heap APIs. Use a unique tiebreaker so payloads are never compared.

• Running median = two balanced heaps — the same idea returns in L52.

Corrective source notes

• heapq documentation pinned to CPython v3.14.0 — max-heap operations are marked added in 3.14; unique entry counts prevent payload comparisons. Freshly checked 2026-10-09, alongside the saved 2026-10-07 documentation snapshot.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.