Python heapq for Coding Interviews: Idioms, Traps, and Real Questions

heapq gives you a priority queue in Python without a class: your heap is a plain list, and a small set of module functions keeps it ordered. That design surprises people the first time. There is no Heap object. heap[0] is always the minimum. There is no decrease-key, no way to delete from the middle, and — until Python 3.14 added a public max-heap family — no max-heap either, which is still the practical reality on the 3.11–3.13 runtimes most interview platforms run. Interviewers know all of this, and the better heap questions are built around exactly those gaps. This guide covers the idioms that fill them, each anchored to a question a real company asked.

One scoping note: this page is about the module. If you want the underlying data structure — what a heap is, when to reach for one over sorting or a BST — start with our heap concept guide and come back here for the Python mechanics.

Key Takeaways

• heapq.heapify runs in O(n), not O(n log n). Building a heap from an existing list is cheaper than n pushes, and interviewers ask you to explain why.
• The size-k min-heap is the workhorse pattern: keep k candidates, evict through heappushpop or a guarded heapreplace, and read the answer at heap[0]. Selection in O(n log k) time and O(k) space, and it survives the streaming follow-up.
• heapq was min-heap-only until Python 3.14 added public heappush_max/heappop_max. Interview platforms mostly still run 3.11–3.13, so the interview answer remains negation: push -x, or negate the numeric key inside a tuple. The private _heapify_max is not an answer on any version.
• Heap entries can be tuples. Comparison is lexicographic, so (cost, index) gives you tie-breaking for free — and a TypeError when the payload isn't comparable, which is why the insertion-counter trick exists.
• heapq cannot update an entry in place. The standard workaround is lazy deletion: push a duplicate with the new priority, keep the authoritative value in a dict, and discard stale entries when they surface at the top.

heapq works on a plain list, and heapify is O(n)

Asked at Akuna Capital — Heapify an array into a max-heap You get the concrete array [6, 15, 2, 4, 3, 8, 19] and must run bottom-up heap construction by hand, using the standard 0-indexed array layout, to produce a max-heap. The deliverable is the final array plus enough intermediate steps to prove you didn't guess.

Questions like this show up at trading firms because they separate people who have called heapify from people who know what it does. There is no code to hide behind.

The layout first. A binary heap stored in a list has no pointers: the children of index i sit at 2i + 1 and 2i + 2, and the parent of i sits at (i - 1) // 2. Here is heapq.heapify([6, 15, 2, 4, 3, 8, 19]) — a min-heap, heapq's default and, before 3.14, its only mode — drawn as the tree the list encodes:

The list is [2, 3, 6, 4, 15, 8, 19]. Every parent is ≤ both children; siblings have no ordering relative to each other. A heapified list is not sorted, and saying so out loud scores points.

Bottom-up construction starts at the last parent, index (n - 2) // 2, and sifts each node down toward the leaves. For Akuna's max-heap version on [6, 15, 2, 4, 3, 8, 19] (n = 7, last parent is index 2):

1. i = 2: 2 vs children 8, 19 → swap with 19 → [6, 15, 19, 4, 3, 8, 2]
2. i = 1: 15 vs children 4, 3 → already larger, no move
3. i = 0: 6 vs children 15, 19 → swap with 19, then 6 (now at index 2) vs 8, 2 → swap with 8 → [19, 15, 8, 4, 3, 6, 2]

Final answer: [19, 15, 8, 4, 3, 6, 2].

Now the complexity claim, because "why is heapify O(n)?" is the standard follow-up. The lazy argument — n nodes, each sift costs O(log n) — gives O(n log n), which is a correct bound but not tight. The tight argument counts by height: a node at height h costs at most h swaps, and there are at most ⌈n / 2^(h+1)⌉ nodes at height h. Half the nodes are leaves and cost zero. Summing h · n / 2^(h+1) over all heights gives a series that converges to O(n). Cheap nodes are plentiful, expensive nodes are rare.

The practical consequence: when you already hold all the data in a list, heapify it. Pushing n items one at a time costs O(n log n) and marks you as someone who memorized heappush without learning the module.

The size-k heap: kth largest without sorting

Asked at Meta — Find the kth largest element Given n unsorted integers and a k between 1 and n, return the kth largest — but the question explicitly demands two designs: an expected-linear selection algorithm and a heap-based one, each with complexity analysis, plus a discussion of which survives when the input becomes a stream.

The heap design is the one this section is about, and the counterintuitive part is the direction: to find the kth largest, you keep a min-heap. The heap holds the k largest values seen so far, and its minimum — heap[0] — is the current answer candidate. Anything smaller than heap[0] can't be in the top k and is discarded without touching the heap.

Here is the canonical template. If you learn one piece of heapq code for interviews, make it this one:

import heapq

def kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)              # O(k) — see previous section
    for x in nums[k:]:               # n - k iterations
        if x > heap[0]:              # only contenders pay the log k
            heapq.heapreplace(heap, x)
    return heap[0]

Trace it on nums = [3, 2, 1, 5, 6, 4], k = 2. Seed and heapify [3, 2] → [2, 3]. Then: 1 is not > 2, skip. 5 > 2 → replace → heap is [3, 5]. 6 > 3 → replace → [5, 6]. 4 is not > 5, skip. Return heap[0] = 5, the second largest. Time O(n log k), space O(k).

Two module functions do the evict-and-insert in one call, and they are not interchangeable:

• heappushpop(heap, x) pushes x, then pops the minimum. If x <= heap[0] it returns x immediately without touching the heap at all — a genuine fast path, which is why the unconditional heapq.heappushpop(heap, x) loop body is a fine alternative to the guarded heapreplace above.
• heapreplace(heap, x) pops first, then pushes. It always returns the old minimum, even when x is smaller than everything in the heap. Use it when you must extract the current minimum regardless — a k-way merge step, or the guarded loop above where you've already checked x > heap[0].

Mixing them up is a real bug, not a style issue: an unconditional heapreplace in the loop above would evict a top-k member to admit a smaller value.

Why interviewers push the streaming follow-up: the comparison below is the actual content of the Meta question, and the size-k heap is the only row that doesn't need the whole input in memory.

Quickselect wins the expected-time race and loses everything else: it's in-place (so it mutates the input), its worst case is quadratic without median-of-medians, and it cannot process a stream. Saying that trade-off unprompted is what the "design two methods" phrasing is fishing for.

No max-heap? Negate

Asked at Meta — Return k smallest elements using heap Up to a million unsorted integers, return the k smallest in ascending order — with O(n log k) time and O(k) space stated as hard requirements, duplicates and negatives in scope, and a follow-up where numbers arrive online and getSmallestK() can be called at any moment.

The stated bounds do the routing for you. O(k) space forbids heapifying all n elements; O(n log k) forbids sorting. You must keep a k-element pool and evict the largest of the pool when a smaller value arrives. That means you need a max-heap, and on the Python your interview platform runs, heapq almost certainly doesn't give you one.

The idiom is negation:

import heapq

def k_smallest(nums, k):
    heap = [-x for x in nums[:k]]     # max-heap in disguise
    heapq.heapify(heap)
    for x in nums[k:]:
        if -x > heap[0]:              # i.e. x < largest of the kept pool
            heapq.heapreplace(heap, -x)
    return sorted(-v for v in heap)   # negate back, then order the output

heap[0] holds the negation of the pool's maximum, so the guard -x > heap[0] reads "x is smaller than the worst thing we're keeping". Negatives in the input are fine, since negation is a bijection on integers. The two failure modes that show up in live interviews: negating on the way in but not on the way out, and negating the guard wrong so the heap silently collects the k largest instead. Trace one element by hand before moving on; it takes fifteen seconds and catches both.

Now the version caveat, because this corner of the module actually changed. Python 3.14 (released October 2025) added a public max-heap family to heapq: heapify_max, heappush_max, heappop_max, heappushpop_max, and heapreplace_max. On 3.14+ you can solve this question with no negation at all. Two reasons negation is still the answer to write in an interview. First, LeetCode, HackerRank, and CoderPad mostly run 3.11–3.13, where the only max-heap machinery is the private, incomplete _heapify_max/_heappop_max pair, and citing private functions reads as trivia, not competence. Second, negation transfers to compound priorities: a tuple key like (-score, name) gets you a max-by-score, min-by-name ordering that heappush_max can't express. Mention the 3.14 functions as a version note, then write the negation.

One more edge worth saying aloud: negation only works on numbers. For strings or rich objects, negate a numeric key inside a tuple, or define __lt__ on a small wrapper class. The tuple route is almost always shorter.

The streaming follow-up costs nothing extra: the loop body already processes one element at a time, so add(x) is the loop body and getSmallestK() is the return line. That's the payoff of choosing the O(k)-space design up front.

Tuple entries: compound priorities and tie-breaking for free

Asked at Pinterest — Implement a min-heap column allocator You have k columns, all starting at height 0, and a sequence of posts with heights. Each post goes into the currently shortest column, with ties broken by the smallest column index, and placement increases that column's height. Return the chosen column per post (or the final heights). It mirrors the masonry-layout column balancing Pinterest's feed is known for.

This is the cleanest real-world showcase of tuple entries. heapq compares tuples the way Python does: element by element, moving right only on ties. So an entry of (height, column_index) implements the entire tie-breaking spec in the problem statement with zero extra code:

import heapq

def assign_posts(k, posts):
    heap = [(0, col) for col in range(k)]   # already heap-ordered — no heapify needed
    out = []
    for h in posts:
        height, col = heapq.heappop(heap)
        out.append(col)
        heapq.heappush(heap, (height + h, col))
    return out

Equal heights fall through to the second tuple slot, and smaller column indices win. O(p log k) for p posts. Note the seed line: a list of (0, 0), (0, 1), … (0, k-1) is already sorted, and any sorted list is a valid heap, so calling heapify on it would be wasted (if harmless) work. Mentioning that is a small, cheap signal that you know the invariant rather than the incantation.

The trap arrives when the tuple's tail isn't comparable. Push (priority, task_dict) twice with equal priorities and Python tries task_dict < other_dict — TypeError, at runtime, only when priorities happen to tie, which makes it a flaky production bug rather than an obvious one. The standard fix is a monotonically increasing counter wedged between priority and payload:

from itertools import count

tie = count()
heapq.heappush(heap, (priority, next(tie), task))

The counter is unique, so comparison never reaches the payload. As a bonus, it makes equal-priority ordering FIFO — often exactly what a scheduler question wants anyway.

nlargest and nsmallest: when the one-liner is the right answer

Asked at NVIDIA — Find Top K Frequent Elements The LeetCode 347 setup: given an integer array, return the k most frequent elements. NVIDIA's version starts with a fixed "top 3" and then asks you to generalize to arbitrary k — a nudge to produce a parameterized solution rather than three hardcoded scans.

Frequency problems are two steps — count, then select — and heapq.nlargest collapses the second step:

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts, key=counts.get)

Iterating a Counter yields its keys, and key=counts.get ranks each element by its frequency. Counting is O(n); the selection is O(m log k) for m distinct values. Under the hood nlargest runs the size-k heap pattern from two sections ago, with two documented shortcuts: k = 1 degenerates to a single max scan, and when the iterable has a known length and k >= n it just sorts. So the complexity you claim in the interview is the honest one, O(n log k), and you also get to say you know why.

When does the one-liner lose? Two cases:

• k close to n. The heap's per-element log k overhead stops paying for itself, and sorted(counts, key=counts.get, reverse=True)[:k] is simpler and often faster (O(m log m) with a lower constant). If k ≥ m they're equivalent anyway, because nlargest falls back to sorting.
• The follow-up asks for O(n). Bucket sort by frequency: an array of n+1 buckets where bucket f holds the elements appearing f times, walked from the top. A single value can account for all n occurrences, so frequencies range up to n and the buckets must be indexed 0 through n; within that bound, no comparison sort is needed. Offering this unprompted after shipping the heap version is the strongest move on this question.

One footgun specific to this problem: nlargest(k, counts.items()) without a key compares (element, count) tuples and ranks by element value first. If you'd rather work with items, it's nlargest(k, counts.items(), key=lambda kv: kv[1]) — then strip the counts off. The key=counts.get form avoids the whole issue.

Retain Top K Elements, asked at Microsoft, is the same selection skeleton with an order-preservation twist: pick the k largest, but output them in their original positions, with a tie rule about which duplicates survive. The heap finds the cutoff; a second pass over the original list applies it. It's a good test of whether you can compose the pattern rather than just recite it.

The frontier heap: k-way merge over sorted structures

Asked at Meta — Find kth smallest pair sum with heaps Two sorted arrays A and B, and a k up to n·m. Return the kth smallest value among all pair sums A[i] + B[j] — without materializing the pairs, with a stated target of O(k log min(n, m)) time and O(min(n, m)) space, and with duplicate sums and the k=1 / k=n·m boundaries called out for discussion.

The size-k heap filters a firehose. The frontier heap does the opposite job: it generates values in sorted order from several sorted sources, lazily. Think of each A[i] as owning a sorted list A[i]+B[0], A[i]+B[1], …. The kth smallest pair sum is the kth element of the merge of those lists, and you never need more than one live candidate per list:

import heapq

def kth_smallest_pair_sum(A, B, k):
    if len(A) > len(B):
        A, B = B, A                     # index the heap over the shorter array
    heap = [(A[i] + B[0], i, 0) for i in range(min(k, len(A)))]
    heapq.heapify(heap)
    for _ in range(k - 1):
        s, i, j = heapq.heappop(heap)
        if j + 1 < len(B):
            heapq.heappush(heap, (A[i] + B[j + 1], i, j + 1))
    return heap[0][0]

Each pop is the next-smallest sum globally; each pop pushes at most one successor, so after the swap the heap never exceeds min(k, min(n, m)) entries and the total is O(k log min(n, m)). The min(k, …) in the seed matters: rows beyond the kth can't contribute to the first k answers. Duplicate sums need no special handling — the heap emits them as separate entries, which is exactly what "duplicates counted by occurrence" asks for.

One structural point worth stating in the interview: every entry (i, j) is pushed by exactly one parent ((i, j-1), or the seed when j = 0), so there's no visited set. Frontier problems where a cell has multiple parents — expanding both (i+1, j) and (i, j+1) from a grid cell — do need one, or the heap fills with duplicates and the count drifts. Knowing which regime you're in is the difference between a clean solution and a subtle overcount.

The same shape solves the sorted-matrix family: seed a heap with each row's head and pop k times. Find kth smallest in a sorted 2D matrix at TikTok is exactly this, and Meta's matrix variant explicitly asks you to compare the heap against binary search on the value range. Counting the O(n) row-head seeding, the heap is O(n + k log n) and the binary search O(n log(max−min)), so the heap wins for small k and loses when k approaches n². For plain list merging, heapq.merge(*lists) is this pattern packaged as a generator: O(log k) per element yielded, nothing materialized.

heapq has no decrease-key — lazy deletion is the answer

Asked at LinkedIn — Solve Cache, Window, and Heap Problems A multi-problem round: a frequency-based cache with get/put in O(1) average time that evicts the least-frequently-used key (recency breaks ties), plus a shortest-covering-substring problem, in one sitting. The cache is where heap-first instincts go to die, and that's the point of asking it.

Here's the module's sharpest limitation. Once an entry is inside the heap, heapq gives you no way to find it (that's an O(n) scan), no way to change its priority, and no way to delete it without breaking the invariant. Real algorithms need this constantly — Dijkstra relaxes distances, an LFU cache bumps frequencies, a scheduler cancels jobs.

The interview-grade workaround is lazy deletion: never touch an entry after pushing it. When a priority changes, push a second entry with the new value and record the truth in a dict. When popping, check the entry against the dict; if they disagree, it's stale — discard and pop again. Dijkstra wears it like this:

import heapq

def dijkstra(adj, src):
    best = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > best.get(u, float("inf")):
            continue                       # stale — a cheaper entry already won
        for v, w in adj[u]:
            nd = d + w
            if nd < best.get(v, float("inf")):
                best[v] = nd
                heapq.heappush(heap, (nd, v))
    return best

The cost: the heap holds up to O(E) entries instead of O(V), so operations are O(log E). Since log E ≤ log V² = 2 log V, that's the same asymptotic class — a small constant-factor tax. In exchange, every operation stays a plain push or pop. For interviews this trade is nearly always right; a hand-rolled indexed heap with sift-up on decrease-key is 40+ lines of bug surface for no asymptotic gain.

Now the LinkedIn cache, and why it's a trap. A heap of (frequency, last_used_tick, key) with lazy invalidation works, but eviction pops cost O(log n) and the problem says O(1) average per operation. Lazy deletion can't get you there. The honest answer is that this problem outgrows heapq: true LFU wants a dict of doubly-linked lists bucketed by frequency, where bump and evict are pointer moves. Recognizing when the heap is the wrong tool — and saying so before writing code — is precisely what a multi-problem round measures. The same boundary shows up in sliding-window maximum: lazy deletion (skip popped entries whose index left the window) is a valid O(n log n) answer, but the monotonic-deque pattern does it in O(n), and the sliding-window guide covers when each applies.

Practice these on PracHub

The routing logic, compressed:

Then drill each branch against the real thing:

• Heap mechanics by hand — Heapify an array into a max-heap (Akuna Capital). No code; can you run sift-down on paper and defend O(n)?
• The size-k template — Find kth largest element in array (Meta). The canonical form, with duplicates called out explicitly.
• Selection plus order preservation — Retain Top K Elements (Microsoft). Uses the heap to find a cutoff, then a second pass to apply it — pattern composition, not recitation.
• nlargest with a key function — Find Top K Frequent Elements (NVIDIA). Counter plus nlargest, then the O(n) bucket-sort follow-up.
• Tuple priorities and tie-breaking — Implement a min-heap column allocator (Pinterest). Lexicographic comparison doing the spec's work for you.
• The frontier heap — Find kth smallest in sorted 2D matrix (TikTok). Row-head seeding, one successor per pop.

For more heap questions filtered by company and role, browse the coding and algorithms bank or search all questions; the wider pattern guides cover the neighboring techniques these problems pivot into.