Heaps and Priority Queues Questions
Binary heaps and priority queues as data structures: min-heap and max-heap, array layout, sift-up and sift-down, push/pop/peek costs, build-heap (heapify) in O(n), and indexed heaps with decrease-key versus lazy deletion of stale entries. Covers the problems where a heap is the intended tool: top-K and kth largest or smallest selection (including over a one-pass stream and under inserts and deletes), sorting an array whose elements are at most k places out of order with a window heap, the two-heap pattern for running and sliding-window medians (invariants, rebalancing, lazy deletion, testing, and extensions to percentiles, weighted medians, custom orderings and merging structures), k-way merge of sorted lists, arrays, files or streams with bounded memory, scheduling by priority with cancellation and reprioritisation, stable priority queues with tie-breaking, and implementing a heap or priority queue with a language library such as heapq or PriorityQueue (including max-heap behaviour from a min-heap). Boundary: graph shortest-path algorithms, approximate quantile sketches, production streaming-system design, and heapsort and quickselect as sorting and selection algorithms are covered elsewhere.
Implement a function in JavaScript to find the kth most frequent element in an array of integers. Provide a solution optimized for average-case time complexity better than O(n log n) where n is array length. State assumptions and complexity.
Sample Answer
The idea
"The kth most frequent element" means: count how many times each distinct value appears, rank the distinct values from most to least frequent, and return the value at position k. Counting is a single pass with a hash map. The only real question is how to pick rank k out of the counts without sorting all of them.
Assumptions
- Rank is by count, highest first. Ties are broken by whichever value appeared first in the array, so the answer is deterministic. (If your interviewer wants a different tie rule, only the tie-break comparison changes.)
- k is 1-based and must be a positive integer. If there are fewer than k distinct values, the function returns
undefined. - n is the array length and d is the number of distinct values (d <= n).
Brute force and the options
Sorting the counts costs O(d log d), which is O(n log n) when most values are distinct. That is the baseline to beat. The alternatives:
| Approach | Time | Extra space | Notes |
|---|---|---|---|
| Sort the (value, count) pairs | O(n + d log d) | O(d) | Simple; worst case O(n log n). |
| Min-heap of size k over the counts | O(n + d log k) | O(d + k) | Faster when k is small. |
| Bucket by frequency | O(n) | O(n) | A count is at most n, so use counts as array indexes. |
| Quickselect on the counts | O(d) average, O(d^2) worst case | O(d) | Pick a pivot count, partition (split) the entries into those ranking above and below it, and continue only in the part that contains rank k; the worst case needs pivots that keep splitting badly, and tie-breaking adds a compare rule. |
The recommended solution is bucketing: it is O(n) in the worst case and has no heap to write. The heap version is included because it is the answer interviewers expect when the counts are huge and k is tiny, since it never holds more than k entries in the heap.
Approach
Bucket: (1) count with a Map, which iterates in insertion order (the order values first appeared); (2) create an array of n + 1 empty lists where buckets[c] holds the values that occurred exactly c times, filled in that order; (3) walk c from n down to 1, counting values as you go, and return the one at rank k.
Heap: keep a min-heap (a tree stored in an array whose root is the smallest item, here "smallest" means worst-ranked) of the k best-ranked values. In the array, the parent of index i sits at index (i - 1) >> 1 (the right shift by one bit halves the number, rounding down) and its children sit at 2i + 1 and 2i + 2. To sift is to move an entry up (swap with its parent) or down (swap with its smaller child) until the order rule holds again. For each distinct value, if the heap has room, add it; otherwise, if the value outranks the root, replace the root. After all values, the root is the worst of the k best, which is exactly rank k.
// Rank distinct values by count (highest first); ties go to the value that appeared first.
// Returns the value at 1-based rank k, or undefined if there are fewer than k distinct values.
function countFirstSeen(nums) {
const counts = new Map(); // a Map iterates in insertion order = order of first appearance
for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
return counts;
}
// O(n) time, O(n) space: bucket by frequency, then walk from the highest frequency down.
function kthMostFrequentBucket(nums, k) {
if (!Number.isInteger(k) || k < 1) throw new RangeError("k must be a positive integer");
const counts = countFirstSeen(nums);
const buckets = Array.from({ length: nums.length + 1 }, () => []); // buckets[c] = values seen c times
for (const [value, c] of counts) buckets[c].push(value);
let rank = 0;
for (let c = nums.length; c >= 1; c--) {
for (const value of buckets[c]) {
if (++rank === k) return value;
}
}
return undefined;
}
// O(n + d log k) time, O(d + k) space (d = distinct values): a min-heap of the k best-ranked entries.
// "worse" means lower count, or equal count but first seen later.
function kthMostFrequentHeap(nums, k, log = false) {
if (!Number.isInteger(k) || k < 1) throw new RangeError("k must be a positive integer");
const heap = [];
const worse = (a, b) => a.count < b.count || (a.count === b.count && a.first > b.first);
const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]); // destructuring swap, no temp variable
const siftUp = (i) => {
while (i > 0) {
const p = (i - 1) >> 1; // parent of index i; ">> 1" halves a whole number, rounding down
if (!worse(heap[i], heap[p])) break;
swap(i, p);
i = p;
}
};
const siftDown = (i) => {
for (;;) {
let m = i;
const l = 2 * i + 1, r = l + 1; // children of index i are at 2i + 1 and 2i + 2
if (l < heap.length && worse(heap[l], heap[m])) m = l;
if (r < heap.length && worse(heap[r], heap[m])) m = r;
if (m === i) return;
swap(i, m);
i = m;
}
};
let first = 0;
for (const [value, count] of countFirstSeen(nums)) {
const entry = { value, count, first: first++ };
if (heap.length < k) {
heap.push(entry);
siftUp(heap.length - 1);
} else if (worse(heap[0], entry)) { // entry outranks the current kth: replace the root
heap[0] = entry;
siftDown(0);
}
if (log) console.log(` value ${value} (x${count}) -> heap [${heap.map((e) => `${e.value}x${e.count}`).join(", ")}]`);
}
return heap.length === k ? heap[0].value : undefined;
}
// Reference: O(d log d) sort by (count desc, first appearance asc).
function kthMostFrequentSort(nums, k) {
const ranked = [...countFirstSeen(nums)].sort((a, b) => b[1] - a[1]); // stable sort (Node 22): equal counts keep their first-appearance order
return ranked[k - 1]?.[0];
}
const nums = [4, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 9];
console.log("counts:", [...countFirstSeen(nums)].map(([v, c]) => `${v}x${c}`).join(" "));
console.log("heap steps for k=3:");
kthMostFrequentHeap(nums, 3, true);
for (const k of [1, 2, 3, 4, 5, 6]) {
console.log(`k=${k}: bucket=${kthMostFrequentBucket(nums, k)} heap=${kthMostFrequentHeap(nums, k)} sort=${kthMostFrequentSort(nums, k)}`);
}
console.log("empty array, k=1:", kthMostFrequentBucket([], 1), kthMostFrequentHeap([], 1));
try { kthMostFrequentBucket(nums, 0); } catch (e) { console.log("k=0:", e.message); }
// Randomised agreement check. The generator below is a linear congruential generator: a tiny
// formula that turns the previous number into the next one, so the same seed gives the same run.
// Math.imul multiplies as exact 32-bit integers and & 0x7fffffff keeps 31 bits, i.e. arithmetic mod 2^31.
let seed = 12345;
const rand = () => (seed = (Math.imul(seed, 1103515245) + 12345) & 0x7fffffff) / 2147483648;
for (let t = 0; t < 2000; t++) {
const arr = Array.from({ length: Math.floor(rand() * 20) }, () => Math.floor(rand() * 8) - 3);
const k = 1 + Math.floor(rand() * 6);
const a = kthMostFrequentBucket(arr, k), b = kthMostFrequentHeap(arr, k), c = kthMostFrequentSort(arr, k);
if (a !== c || b !== c) throw new Error(`mismatch ${JSON.stringify(arr)} k=${k}: ${a} ${b} ${c}`);
}
console.log("2000 random arrays: all three agree");
Output:
counts: 4x4 1x2 2x3 3x2 9x1
heap steps for k=3:
value 4 (x4) -> heap [4x4]
value 1 (x2) -> heap [1x2, 4x4]
value 2 (x3) -> heap [1x2, 4x4, 2x3]
value 3 (x2) -> heap [1x2, 4x4, 2x3]
value 9 (x1) -> heap [1x2, 4x4, 2x3]
k=1: bucket=4 heap=4 sort=4
k=2: bucket=2 heap=2 sort=2
k=3: bucket=1 heap=1 sort=1
k=4: bucket=3 heap=3 sort=3
k=5: bucket=9 heap=9 sort=9
k=6: bucket=undefined heap=undefined sort=undefined
empty array, k=1: undefined undefined
k=0: k must be a positive integer
2000 random arrays: all three agree
Worked trace (from the output)
Counts are 4x4 1x2 2x3 3x2 9x1. The ranking is 4 (count 4), then 2 (count 3), then 1 and 3 (both count 2; 1 appeared first), then 9. That is why k=3 gives 1, k=4 gives 3, k=5 gives 9, and k=6 gives undefined. In the bucket version, buckets[4] = [4], buckets[3] = [2], buckets[2] = [1, 3], buckets[1] = [9]; walking down from the top and counting ranks reaches the same answers.
The heap version on the same data with k = 3 (the heap steps for k=3 lines of the output; each entry is valuexcount, and the root, listed first, is the worst-ranked of the kept three):
- Value 4 (count 4) is added:
[4x4]. - Value 1 (count 2) is added and is worse-ranked than 4, so it sifts up to the root:
[1x2, 4x4]. - Value 2 (count 3) is added at the end; it outranks the root 1x2, so it stays below it:
[1x2, 4x4, 2x3]. The heap now holds k = 3 entries. - Value 3 (count 2) ties the root's count but appeared later than 1, so it ranks below the root and is ignored. The heap does not change.
- Value 9 (count 1) ranks below the root and is ignored.
- The root is
1x2, the worst-ranked of the three best, which is rank 3: the answer is 1, as in thek=3line.
Complexity of the shipped code
- Bucket: counting O(n); building n + 1 buckets O(n); the walk visits at most n + d slots. Time O(n), space O(n).
- Heap: counting O(n), then each of d values costs at most O(log k) for a sift (moving an item up or down the tree to restore order). Time O(n + d log k), space O(d) for the map plus O(k) for the heap.
- Both beat a full sort asymptotically when many values are distinct. When k is close to d, the heap's log k approaches log d and the advantage disappears; bucketing stays O(n).
Edge cases and common mistakes
- Empty array: returns
undefinedrather than throwing.kof 0, negative or fractional throws aRangeError. - All values equal: one distinct value, so only k = 1 returns something.
- Ties: without a stated rule, two correct programs can disagree. Note the tie rule out loud.
- Using a plain object instead of
Mapto count: integer-like keys are reordered ascending by the engine and become strings, which breaks first-appearance order and the tie-break. UseMap. - Confusing "kth most frequent element" with "top k most frequent elements". The same counts answer both; for the top k, return all the values in the first k ranks (the heap's contents) instead of only the last.
- Using
sort()on numbers without a comparator in JavaScript, which sorts them as strings.
Running the code
node kth_frequent.js
Node 22, no packages.
Python's heapq only provides a min-heap. How do you get max-heap behaviour from it, and what pitfalls should you watch for with floats, ties, and custom objects? Show a push and pop.
Sample Answer
The idea
A heap is a tree stored in a plain list where the item at index 0 is always the "best" one, and pushing or popping keeps that true in O(log n) time. Python's heapq module implements a min-heap (index 0 is the smallest) in Python 3.12 and every release before 3.14; Python 3.14 added documented max-heap functions with a _max suffix (heapify_max, heappush_max, heappop_max, heapreplace_max, heappushpop_max), which remove the need for any trick on 3.14 or later. The trick below works on every version, so it is the one to know. To get max-heap behaviour, flip the order your items are compared in. For numbers, the usual trick is to store -x and negate again when reading: the smallest negated value is the largest original value.
Push and pop
Step by step: push -n instead of n; the largest original value is -heap[0] (a peek, O(1)); -heappop(heap) removes and returns it (O(log n)). Pushing is also O(log n), and building a heap from an existing list with heapq.heapify is O(n). The reason it beats n separate pushes (O(n log n)): heapify sifts each parent down, starting from the last one, and about half of all entries are leaves that need no work, a quarter can move at most one level, an eighth at most two, so the total stays proportional to n. For example [4, 3, 2, 1] becomes [1, 3, 2, 4] after heapify.
The code below uses itertools.count() (an endless counter that yields 0, 1, 2, ... each time you ask for the next value) and @dataclass (a decorator that gives a small class an automatic constructor and a readable form, so Task("a") stores a name). It also shows the three pitfalls the question asks about: floats, ties and custom objects.
import heapq
import itertools
from dataclasses import dataclass
# 1. Max-heap by negating the key
nums = [3, 9, 4, 9, 1]
max_heap = []
for n in nums:
heapq.heappush(max_heap, -n)
print("max-heap array:", max_heap)
print("pop largest:", -heapq.heappop(max_heap))
print("next largest:", -max_heap[0])
# 2. Pitfall: floats. -inf is fine, but nan breaks the ordering
print("negated inf:", -float("inf"))
h = []
for x in [1.0, float("nan"), 3.0, 2.0]:
heapq.heappush(h, -x)
print(" after push", -x, "->", h)
popped = []
while h:
popped.append(heapq.heappop(h))
print(" after pop", popped[-1], "->", h)
print("nan in heap, pops in order:", popped)
# 3. Pitfall: ties force Python to compare the objects themselves
@dataclass
class Task:
name: str
heap = []
heapq.heappush(heap, (-5, Task("a")))
try:
heapq.heappush(heap, (-5, Task("b")))
except TypeError as e:
print("tie error:", e)
# 4. Fix: a unique counter breaks ties before the object is reached
counter = itertools.count()
heap = []
for prio, name in [(5, "a"), (9, "b"), (5, "c")]:
heapq.heappush(heap, (-prio, next(counter), Task(name)))
while heap:
neg, order, task = heapq.heappop(heap)
print("pop", -neg, order, task.name)
# 5. Alternative for keys you cannot negate (strings): reverse the comparison
class MaxItem:
def __init__(self, key, value=None):
self.key, self.value = key, value
def __lt__(self, other): # heapq only ever uses <
return self.key > other.key
h = []
for k in ["pear", "apple", "zebra"]:
heapq.heappush(h, MaxItem(k))
print("string max-heap pops:", [heapq.heappop(h).key for _ in range(3)])
Output:
max-heap array: [-9, -9, -4, -3, -1]
pop largest: 9
next largest: 9
negated inf: -inf
after push -1.0 -> [-1.0]
after push nan -> [-1.0, nan]
after push -3.0 -> [-3.0, nan, -1.0]
after push -2.0 -> [-3.0, nan, -1.0, -2.0]
after pop -3.0 -> [-2.0, nan, -1.0]
after pop -2.0 -> [nan, -1.0]
after pop nan -> [-1.0]
after pop -1.0 -> []
nan in heap, pops in order: [-3.0, -2.0, nan, -1.0]
tie error: '<' not supported between instances of 'Task' and 'Task'
pop 9 1 b
pop 5 0 a
pop 5 2 c
string max-heap pops: ['zebra', 'pear', 'apple']
Reading the output
- The array
[-9, -9, -4, -3, -1]is the heap layout of the negated values. A heap is only partially ordered, so you can print the list but should not expect it to be fully sorted in general; only index 0 is guaranteed to be the extreme. pop largest: 9thennext largest: 9shows duplicates: the two 9s are both stored.
Pitfalls
Floats. In Python, negating a float is exact, so there is no overflow: -float("inf") is -inf, and infinities work as keys. (In a language with fixed-width integers, numbers stored in a set number of bits such as 32 that wrap around once they exceed their range, negating the smallest possible integer overflows, so use a comparator, a function you pass to the queue that defines which of two items comes first, instead of negation there.) The real float trap is nan: every comparison with nan is false, so the heap cannot order it. The output shows the pops coming out as -3.0, -2.0, nan, -1.0, which is not sorted. Here is how it happens, from the after push and after pop lines. The pushes put -1.0, nan, -3.0, -2.0 into the array. -3.0 bubbles up past -1.0 to the root because -3.0 < -1.0 is true. -2.0 is placed under nan, and the check -2.0 < nan is false, so it stays there instead of moving up. The array [-3.0, nan, -1.0, -2.0] looks fine to the heap, which only ever asks <. Popping -3.0 moves the last entry -2.0 to the root and promotes -1.0, giving [-2.0, nan, -1.0], and the next pop gives -2.0. Now nan is at the root and -1.0 below it: since no comparison involving nan is ever true, nan is never swapped away from the root, so it comes out before -1.0. Reject or filter nan before pushing.
Ties and custom objects. heapq compares tuples element by element. If two priorities are equal, Python moves on to compare the next element, and if that is an object with no < the push raises TypeError (shown above as tie error). The fix is to put a unique, increasing counter between the priority and the object, (-priority, next(counter), task). The counter is never equal to another counter, so the object is never compared, and equal priorities also pop in insertion order (first in, first out: a before c in the output).
Keys you cannot negate. Strings and arbitrary objects cannot be negated. Wrap them in a small class whose __lt__ (the "less than" method, the only comparison heapq uses) returns the opposite answer, as MaxItem does. The output ['zebra', 'pear', 'apple'] is descending order.
Do not call the underscore helpers such as heapq._heappop_max on Python 3.13 or earlier. They are undocumented, can change without notice, and are not part of the public API there. On Python 3.14 or later use the documented heappop_max family instead, on a list built with heapify_max or heappush_max.
Complexity
push and pop: O(log n); peek: O(1); heapify on n items: O(n); the negation adds O(1) per operation.
Common mistakes
- Forgetting to negate on the way out, so you return
-9instead of9. - Using the max-heap for a top-k-smallest or top-k-largest problem without checking which direction you need. To track the k largest, keep a min-heap of size k and compare new items against its top: the entry you may need to throw away is the smallest of the k you are keeping, and a min-heap keeps exactly that entry at index 0.
- Calling
heapq.heappushon a list that was not built as a heap, for example one you sorted in descending order. A list sorted ascending is already a valid min-heap, because every parent sits at an earlier index than its children and so is no larger ([1, 2, 3, 4, 5]is unchanged byheapify); a descending one is not.
Running the code
python3 max_heap_heapq.py
Python 3.12, standard library only.
You have written a two-heap running median. How would you test it? Describe the unit tests, the edge cases that tend to break it, how you would compare it against a simple brute-force median on random streams, and how you would check its invariants after every insertion.
Sample Answer
The idea in plain words
A two-heap running median keeps a max-heap small (the lower half, stored negated because Python's heapq is a min-heap) and a min-heap large (the upper half). Its correctness rests on three invariants, which are rules that must be true after every insert: (1) small has the same number of values as large, or one more; (2) both arrays really are heaps; (3) every value in small is at most every value in large. If the invariants hold, the median is read from the tops. So a good test plan checks the invariants directly, checks answers against something obviously correct, and then checks that the tests themselves can fail.
A five-layer plan
Layers 1 to 4 answer how to test the structure: known answers, edge streams, rule checks and a brute-force comparison. Layer 5 adds confidence in the tests themselves.
- Unit tests with hand-computed answers. The stream
5, 15, 1, 3must give medians5, 10, 5, 4. Few lines, and they document the intent. - Edge-case streams (listed below), each compared with the ground truth after every insert.
- An invariant validator called after every insert (in an array-stored heap the parent of index
iis at(i - 1) // 2, so the validator checks that no parent is larger than its child). It returns the list of broken rules, so a failure says what broke and where, not only that the median is wrong. - Differential testing against a brute-force reference. Feed random streams to the heap version and to a sorted list kept with
bisect.insort(O(n) per insert, but too simple to be wrong), and compare the medians after every insert. Seeded randomness makes failures reproducible. Property-based testing libraries such as Hypothesis automate this: they generate many random inputs and, when one fails, shrink it, meaning they repeatedly simplify the failing input while it still fails until a minimal example remains. The code below does the same with the standard library and a small shrinker (delete elements, then move values toward zero); the walk-through after the output shows it step by step. - Mutation check, which means testing the tests. Deliberately break the implementation in the ways people really do and confirm that the tests fail. A test suite that has never been seen failing proves little.
Edge cases that tend to break it
- Empty stream: define the behaviour (raise
ValueError) and test it. - One value and two values: the first even-sized median and the first rebalance.
- All values equal, and many duplicates: ties at the boundary between the halves.
- Ascending and descending input: every new value lands on the same side.
- Negative numbers and zero: sign errors in the negation trick hide on positive data, and
0is falsy in Python, soif not topstyle checks are wrong. - Floats: the even-size median is the mean of two middles.
- Very large values: Python ints do not overflow, but a port to a fixed-width language must average with floating-point halves,
a / 2.0 + b / 2.0, and not(a + b) / 2, becausea + bcan overflow (integer halves,a / 2 + b / 2on ints, would drop the odd bit).
The code
The file holds the implementation, six broken copies (sign errors, a sizing error, a wrong rebalance threshold, a wrong even-count median and a plain list append where a heap push belongs, all mistakes that engineers really make), the ground-truth class, the invariant validator, the harness and the shrinker. Its first lines trace the small example.
import bisect
import heapq
import random
class RunningMedian:
def __init__(self):
self.small = [] # lower half, max-heap stored as negated values
self.large = [] # upper half, min-heap
def add(self, x):
heapq.heappush(self.small, -x)
heapq.heappush(self.large, -heapq.heappop(self.small)) # move the largest of the lower half up
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large)) # keep small the same size or one bigger
def median(self):
if not self.small:
raise ValueError("median of an empty stream")
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2
# Deliberately broken copies, used to prove the tests can fail.
class ForgotNegationOnMove(RunningMedian):
def add(self, x):
heapq.heappush(self.small, -x)
heapq.heappush(self.large, heapq.heappop(self.small)) # stored value is negative: sign not undone
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
class ForgotNegationOnRebalance(RunningMedian):
def add(self, x):
heapq.heappush(self.small, -x)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, heapq.heappop(self.large)) # pushed without negating: wrong sign in small
class NoSizeRebalance(RunningMedian):
def add(self, x):
if not self.small or x <= -self.small[0]:
heapq.heappush(self.small, -x)
else:
heapq.heappush(self.large, x)
class LowerMiddleOnly(RunningMedian):
def median(self):
if not self.small:
raise ValueError("median of an empty stream")
return float(-self.small[0])
class WrongRebalanceThreshold(RunningMedian):
def add(self, x):
heapq.heappush(self.small, -x)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) >= len(self.small): # >= instead of >: halves swap sizes
heapq.heappush(self.small, -heapq.heappop(self.large))
class AppendInsteadOfPush(RunningMedian):
def add(self, x):
heapq.heappush(self.small, -x)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
self.small.append(-heapq.heappop(self.large)) # plain append skips the sift: small may stop being a heap
class SortedListMedian:
"""Ground truth: keep a sorted list with bisect.insort (O(n) per insert, but obviously right)."""
def __init__(self):
self.values = []
def add(self, x):
bisect.insort(self.values, x)
def median(self):
n = len(self.values)
if n == 0:
raise ValueError("median of an empty stream")
return float(self.values[n // 2]) if n % 2 else (self.values[n // 2 - 1] + self.values[n // 2]) / 2
def violations(m):
"""Return every broken invariant of a RunningMedian (an empty list means all hold)."""
found = []
small = [-v for v in m.small] # values of the lower half
if len(m.small) - len(m.large) not in (0, 1):
found.append(f"size rule: len(small)={len(m.small)}, len(large)={len(m.large)}")
for name, heap in (("small", m.small), ("large", m.large)):
for i in range(1, len(heap)):
if heap[(i - 1) // 2] > heap[i]:
found.append(f"{name} is not a valid heap at index {i}")
break
if small and m.large and max(small) > min(m.large):
found.append(f"order rule: max(lower)={max(small)} > min(upper)={min(m.large)}")
return found
def run(cls, stream, checks=("invariants", "median")):
"""Feed the stream; report the first problem found by the chosen checks, or None."""
m, truth = cls(), SortedListMedian()
for i, x in enumerate(stream):
m.add(x); truth.add(x)
if "invariants" in checks:
broken = violations(m)
if broken:
return f"after {i + 1} values: {broken[0]}"
if "median" in checks and m.median() != truth.median():
return f"after {i + 1} values: median {m.median()} but expected {truth.median()}"
return None
def shrink(cls, stream):
"""Greedy shrinking: delete elements, then move values toward 0, while the stream still fails."""
stream = list(stream)
changed = True
while changed:
changed = False
for i in range(len(stream)):
shorter = stream[:i] + stream[i + 1:]
if shorter and run(cls, shorter):
stream, changed = shorter, True
break
else:
for i, v in enumerate(stream):
for smaller in (0, v // 2, v - 1 if v > 0 else v + 1):
if abs(smaller) < abs(v) and run(cls, stream[:i] + [smaller] + stream[i + 1:]):
stream[i], changed = smaller, True
break
if changed:
break
return stream
def trace(stream):
m = RunningMedian()
for x in stream:
m.add(x)
print(f"add {x:>2}: lower half {sorted((-v for v in m.small), reverse=True)}, upper half {sorted(m.large)}, "
f"median {m.median()}, violations {violations(m)}")
EDGE_STREAMS = {
"one value": [5],
"two values": [3, 1],
"all equal": [7] * 6,
"ascending": list(range(8)),
"descending": list(range(8, 0, -1)),
"alternating extremes": [100, -100, 99, -99, 98],
"negatives and zero": [-5, 0, -5, 0, -1],
"floats": [0.5, 0.25, 2.0, 1.0],
}
def random_streams(count, seed):
rng = random.Random(seed)
for _ in range(count):
n = rng.randint(1, 30)
spread = rng.choice([2, 5, 1000]) # a small spread forces many duplicates
yield [rng.randint(-spread, spread) for _ in range(n)]
if __name__ == "__main__":
trace([5, 15, 1, 3])
print()
m = RunningMedian()
try:
m.median()
except ValueError as e:
print("empty stream raises ValueError:", e)
for name, stream in EDGE_STREAMS.items():
assert run(RunningMedian, stream) is None, name
print(f"{len(EDGE_STREAMS)} edge-case streams pass")
assert all(run(RunningMedian, s) is None for s in random_streams(5000, seed=1))
print("5000 random streams: median equals the sorted-list median and every invariant holds after every insert")
print("\nDo the tests catch each broken copy?")
for bad in (ForgotNegationOnMove, ForgotNegationOnRebalance, NoSizeRebalance, LowerMiddleOnly, WrongRebalanceThreshold, AppendInsteadOfPush):
edge_hit = any(run(bad, s) for s in EDGE_STREAMS.values())
by_median = sum(1 for s in random_streams(500, seed=1) if run(bad, s, checks=("median",)))
by_invariants = sum(1 for s in random_streams(500, seed=1) if run(bad, s, checks=("invariants",)))
failing = next(s for s in random_streams(5000, seed=1) if run(bad, s))
minimal = shrink(bad, failing)
print(f"{bad.__name__}: edge cases {'catch' if edge_hit else 'miss'} it; "
f"of 500 random streams, median check fails {by_median}, invariant check fails {by_invariants}")
print(f" minimal failing stream {minimal} -> {run(bad, minimal)}")
Run, it prints:
add 5: lower half [5], upper half [], median 5.0, violations []
add 15: lower half [5], upper half [15], median 10.0, violations []
add 1: lower half [5, 1], upper half [15], median 5.0, violations []
add 3: lower half [3, 1], upper half [5, 15], median 4.0, violations []
empty stream raises ValueError: median of an empty stream
8 edge-case streams pass
5000 random streams: median equals the sorted-list median and every invariant holds after every insert
Do the tests catch each broken copy?
ForgotNegationOnMove: edge cases catch it; of 500 random streams, median check fails 498, invariant check fails 431
minimal failing stream [-1] -> after 1 values: median 1.0 but expected -1.0
ForgotNegationOnRebalance: edge cases catch it; of 500 random streams, median check fails 482, invariant check fails 311
minimal failing stream [-1] -> after 1 values: median 1.0 but expected -1.0
NoSizeRebalance: edge cases catch it; of 500 random streams, median check fails 455, invariant check fails 468
minimal failing stream [0, 0] -> after 2 values: size rule: len(small)=2, len(large)=0
LowerMiddleOnly: edge cases catch it; of 500 random streams, median check fails 474, invariant check fails 0
minimal failing stream [0, -1] -> after 2 values: median -1.0 but expected -0.5
WrongRebalanceThreshold: edge cases catch it; of 500 random streams, median check fails 474, invariant check fails 480
minimal failing stream [0, 0] -> after 2 values: size rule: len(small)=2, len(large)=0
AppendInsteadOfPush: edge cases catch it; of 500 random streams, median check fails 456, invariant check fails 461
minimal failing stream [0, 0, -1] -> after 3 values: small is not a valid heap at index 1
Reading the output
- The trace shows the medians 5.0, 10.0, 5.0, 4.0 for
5, 15, 1, 3, with an empty violation list after every insert. Afteradd 1the halves are[5, 1]and[15], afteradd 3they are[3, 1]and[5, 15]: the value 5 crossed from the lower to the upper half during the rebalance. - The suite passes on the correct implementation: the empty-stream error, 8 edge streams, and 5000 random streams.
- Every broken copy is caught, and the shrinker reduces the failing stream to one, two or three values.
ForgotNegationOnMove(the negation applied on the way intosmallbut not undone when the value moves tolarge) fails on[-1]with median1.0instead of-1.0.ForgotNegationOnRebalanceis the mirror image on the other move. - The two kinds of check are not interchangeable.
LowerMiddleOnlyreturns the lower middle for even counts: the invariant check fails 0 times out of 500 random streams (the heaps are perfectly valid), while the median comparison fails 474 times. Conversely,NoSizeRebalanceandWrongRebalanceThresholdare caught by the size rule right after the second insert, before a wrong median is even produced.AppendInsteadOfPushis the copy that reaches the heap rule: it fillssmallwith a plain list append, so no size or ordering rule breaks at first, and the shortest failing stream[0, 0, -1]is reported assmall is not a valid heap at index 1(the stored values insmallend up as[1, 0], a parent above a smaller child). Without that mutant the heap-shape check in the validator would never be seen failing. Keep both checks.
How the shrinker reaches [-1]
shrink tries to make a failing stream smaller while it still fails. It first tries deleting each element in turn and keeps the first deletion that still fails, then starts over; only when no deletion works does it try replacing a value by 0, by v // 2 (floor division, so -478 // 2 is -239) or by one step toward zero, accepting the first candidate that is closer to zero and still fails. For ForgotNegationOnMove, a real run starts from the failing stream [735, 643, 564, -871, -478] (median -735.0 instead of 735.0 after one insert). Deleting index 0 still fails, four times, leaving [-478]; no further deletion is possible because an empty stream is not allowed. Then values shrink: -478 becomes -239, -120, -60, -30, -15, -8, -4, -2, -1, and at -1 the candidates 0 (the test passes on [0], since the sign bug is invisible there) and -1 // 2, which is still -1, make no progress, so the result is [-1].
Why [-1] fails, step by step. add(-1) pushes the stored value 1 onto small. The buggy move pops it and pushes it onto large without negating, so large holds 1, which reads as the value +1 instead of -1. Then large is longer than small, so the rebalance pops it and pushes -1 onto small. The stored -1 reads as the value +1, so median() returns 1.0 while the truth is -1.0. For NoSizeRebalance the minimal stream is [0, 0]: the second 0 is not greater than the top of small, so it also goes into small, leaving sizes 2 and 0, which the size rule reports.
Complexity of the test code
The validator is O(n) per call (it scans both arrays), so calling it after every insert makes a stream of n values cost O(n^2). That is acceptable in tests (streams of at most 30 values here) and wrong in production code. The sorted-list reference costs O(n) per insert because insort shifts elements.
Common mistakes in testing this structure
- Testing only the median value on short streams: size-rule bugs can be invisible for a while.
- Random data with a wide value range only: duplicates, the tie cases, never occur. The generator above picks small spreads on purpose.
- A reference that shares code with the implementation (for example another heap): it fails the same way.
- A random test with no fixed seed: a failure cannot be reproduced. Seed it and print the seed.
- Never confirming that the test can fail (the mutation check).
Running the code
python test_median.py
Python 3.12, standard library only (bisect, heapq, random). No install or config needed.
Write a Python function that returns the k largest values from a stream of numbers, given as a generator you can read only once, in descending order. Use O(k) extra memory and O(n log k) time, and do not store the whole stream. Explain why a min-heap of size k is the right tool and what happens to each incoming value.
Sample Answer
The idea in plain words
You can read the stream only once and may keep only k values, so you must decide on the spot, for every incoming number, whether it belongs among the k largest seen so far. To decide, you only need to compare it with the smallest member of the current top k. If it is bigger, it earns a place and that smallest member is evicted. If not, it is dropped forever.
A min-heap (a binary tree stored in an array where every parent is less than or equal to its children, so the smallest value is always at index 0) gives you exactly that "smallest of the current top k" in O(1), and lets you swap it out in O(log k). That is why a min-heap, and not a max-heap, is the right tool for the k largest: the root is the gatekeeper, the weakest member of the club.
The brute force and why it is not enough
Collect everything into a list, sort descending, take the first k. That is O(n log n) time and O(n) memory, and the memory is the real problem: the stream may be larger than RAM, or never end. Python's heapq.nlargest(k, stream) already does exactly this, so in an interview you write the heap yourself and then mention that.
The approach
For each incoming value x:
- If the heap holds fewer than k values, push x.
- Otherwise compare x with
heap[0], the smallest of the current top k. Ifx > heap[0], callheapq.heapreplace(heap, x), which removes the root and inserts x with a single sift (one pass down the tree) instead of a pop followed by a push. - Otherwise discard x.
After the stream ends, sort the (at most k) values descending. The class TopK in the code is the incremental version: insert is the same three steps, and top() returns the current top k sorted descending, so memory stays proportional to k whatever the number of inserts.
The code
import heapq
import random
def top_k_stream(stream, k, trace=False):
"""Return the k largest values of a one-pass iterable, largest first."""
if k <= 0:
return []
heap = [] # min-heap: heap[0] is the smallest of the current top k
for x in stream:
if len(heap) < k:
heapq.heappush(heap, x)
action = "push (heap not full)"
elif x > heap[0]:
heapq.heapreplace(heap, x) # pop the root and push x in one sift
action = "replace root"
else:
action = "discard"
if trace:
print(f"read {x:>3}: {action:<21} heap={sorted(heap)}")
return sorted(heap, reverse=True)
class TopK:
"""Incremental version: insert values, read the current top k."""
def __init__(self, k):
self.k = k
self._heap = []
def insert(self, x):
if len(self._heap) < self.k:
heapq.heappush(self._heap, x)
elif self._heap and x > self._heap[0]:
heapq.heapreplace(self._heap, x)
def top(self):
return sorted(self._heap, reverse=True) # O(k log k), memory stays O(k)
def numbers():
yield from [5, 1, 9, 3, 7, 7, 2, 8, 6, 4]
print(top_k_stream(numbers(), 3, trace=True))
# k larger than the stream, k = 0, ties
print(top_k_stream(iter([4, 2]), 5), top_k_stream(iter([4, 2]), 0), top_k_stream(iter([7, 7, 7, 1]), 2))
# incremental API, for example the slowest requests seen so far
slowest = TopK(3)
for ms in [120, 80, 450, 95, 300, 510, 40]:
slowest.insert(ms)
print("after", ms, "->", slowest.top())
# check against sorting everything, on random streams with duplicates
rng = random.Random(7)
for _ in range(500):
data = [rng.randint(-20, 20) for _ in range(rng.randint(0, 30))]
k = rng.randint(0, 8)
assert top_k_stream(iter(data), k) == sorted(data, reverse=True)[:k]
print("500 random streams match sorted(...)[:k]")
Output:
read 5: push (heap not full) heap=[5]
read 1: push (heap not full) heap=[1, 5]
read 9: push (heap not full) heap=[1, 5, 9]
read 3: replace root heap=[3, 5, 9]
read 7: replace root heap=[5, 7, 9]
read 7: replace root heap=[7, 7, 9]
read 2: discard heap=[7, 7, 9]
read 8: replace root heap=[7, 8, 9]
read 6: discard heap=[7, 8, 9]
read 4: discard heap=[7, 8, 9]
[9, 8, 7]
[4, 2] [] [7, 7]
after 120 -> [120]
after 80 -> [120, 80]
after 450 -> [450, 120, 80]
after 95 -> [450, 120, 95]
after 300 -> [450, 300, 120]
after 510 -> [510, 450, 300]
after 40 -> [510, 450, 300]
500 random streams match sorted(...)[:k]
Worked trace
The trace lines above come from top_k_stream(numbers(), 3, trace=True), with k = 3. The heap contents are printed sorted for readability; the root is the first (smallest) value shown.
- Reads 5, 1, 9 fill the heap, so it holds
[1, 5, 9]with root 1. - Read 3 beats the root 1, so 1 is evicted:
[3, 5, 9]. - Read 7 beats root 3:
[5, 7, 9]. The second 7 beats root 5:[7, 7, 9]. - Read 2 is below the root 7, so it is discarded and the heap is unchanged.
- Read 8 beats root 7:
[7, 8, 9]. Reads 6 and 4 are discarded. - The final sort descending gives
[9, 8, 7].
The TopK run shows the same logic as a live read-out: after 95 arrives the three slowest requests are [450, 120, 95], and the later 40 changes nothing.
Complexity
- Time: each of the n values costs one comparison with the root, and at most one O(log k)
heappushorheapreplace. Total O(n log k), plus O(k log k) for the final sort. Since k is at most n, this is never worse than sorting everything, and when k is small it is close to O(n). - Space: the heap never holds more than k values, so O(k) extra memory. The returned list is also size k. Nothing proportional to n is stored.
TopK.top()costs O(k log k) per call because it sorts a copy. If reads are much more frequent than inserts, cache the sorted list and rebuild it only after an insert that actually changed the heap.
Edge cases and common mistakes
- k larger than the stream: the heap never fills, so you get every value, sorted (the
[4, 2]line). - k = 0 (or negative): return an empty list immediately. Without that guard,
heap[0]on an empty heap raisesIndexError. - Ties: with
x > heap[0]an equal value is discarded. For plain numbers the returned values are the same either way, because equal numbers are interchangeable. If equal keys belong to different items (requests with the same latency, say), which of them stays is not determined by the comparison alone: switching to>=does not give a "newest wins" rule either, since it replaces whichever equal item happens to sit at the root, not the oldest one. To get a definite rule, push(key, arrival_number)pairs: pairs never tie, so the k largest pairs are exactly the largest keys with the newest items winning among equal keys. - Empty stream: returns
[]. - A frequent mistake is a max-heap of size n or k. A max-heap of size k puts the largest value at the root, which tells you nothing about who to evict.
- Another is
heappopthenheappushon every replacement. It works, but does two sifts whereheapreplacedoes one. - Up to Python 3.13,
heapqprovides min-heap functions only (Python 3.14 added max-heap counterparts such asheappush_max,heappop_maxandheapify_max), and a min-heap is exactly what is needed here. For the k smallest you would negate the values, flip the comparison, or on 3.14 use the max-heap functions.
Running the code
python3 top_k.py
No packages are needed beyond the standard library (heapq, random); the file runs unchanged on Python 3.12.
Given a stream of numbers and an integer k, maintain the kth smallest element seen so far after each new number. Which heap would you keep, what size, and what do insert and query cost? Implement it.
Sample Answer
The idea
The kth smallest value only depends on the k smallest values seen so far. Anything bigger than all of those can never become the kth smallest later, because the k smaller values stay in the stream forever. So keep just those k values, and arrange them so the largest of them is instantly available: that largest of the k smallest is exactly the kth smallest.
The structure for "instant access to the largest, cheap insert and removal" is a max-heap (a tree stored in a list whose top is always the biggest item). Size it at k, not n. Python's heapq is a min-heap in Python 3.12 and every release before 3.14 (3.14 added _max functions such as heappush_max, but negation works on every version), so store negated values.
Brute force and why it is not enough
Sorting everything after each new number costs O(n log n) per update, and bisect.insort into a sorted list costs O(n) per update because items must shift. A heap of size k costs O(log k) per update and uses only O(k) memory, which matters when the stream is huge and k is small.
Approach
- If the heap holds fewer than k values, push the new one. Until k values have arrived the kth smallest does not exist, so the query returns
None. - Otherwise compare with the top (the current kth smallest). If the new value is smaller, it pushes the old top out of the "k smallest": replace the top with it. If it is equal or larger, discard it; it cannot change the answer.
- The answer is the heap's top.
heapq.heapreplace pops the top and pushes the new item in one operation, which is O(log k) and cheaper than a separate pop and push.
import heapq
class KthSmallest:
"""Keeps the k smallest values seen so far in a max-heap (stored negated).
The heap's top is then the kth smallest."""
def __init__(self, k):
if k < 1:
raise ValueError("k must be at least 1")
self.k = k
self.heap = [] # negated values of the k smallest so far
def add(self, x):
"""Insert x and return the kth smallest so far, or None if fewer than k values were seen."""
if len(self.heap) < self.k:
heapq.heappush(self.heap, -x)
elif x < -self.heap[0]: # x beats the current kth smallest
heapq.heapreplace(self.heap, -x) # pop the old top and push x in one O(log k) step
return self.query()
def query(self):
return -self.heap[0] if len(self.heap) == self.k else None
kth = KthSmallest(3)
for x in [7, 2, 9, 4, 4, 1, 8]:
result = kth.add(x)
print(f"add {x}: 3 smallest={sorted(-v for v in kth.heap)} kth smallest={result}")
Output:
add 7: 3 smallest=[7] kth smallest=None
add 2: 3 smallest=[2, 7] kth smallest=None
add 9: 3 smallest=[2, 7, 9] kth smallest=9
add 4: 3 smallest=[2, 4, 7] kth smallest=7
add 4: 3 smallest=[2, 4, 4] kth smallest=4
add 1: 3 smallest=[1, 2, 4] kth smallest=4
add 8: 3 smallest=[1, 2, 4] kth smallest=4
Worked trace (from the output)
With k = 3:
- After 7 and 2 only two values have arrived, so there is no 3rd smallest yet.
- After 9 the three values are {2, 7, 9}, and the largest of them, 9, is the 3rd smallest.
- Add 4: 4 < 9, so 9 is evicted and the set becomes {2, 4, 7}; answer 7.
- Add 4 again: 4 < 7, so 7 is evicted: {2, 4, 4}; answer 4. Duplicates are kept, since two equal values are two distinct entries in sorted order.
- Add 1: it evicts 4, giving {1, 2, 4}; answer 4.
- Add 8: 8 is not smaller than 4, so it is ignored; the answer stays 4.
Complexity
- Insert: O(log k) (one
heappushwhile filling,heapreplaceafterwards, on a heap of at most k items). Worst case happens when each new value is smaller than the top. - Query: O(1), read the top.
- Space: O(k), regardless of how many values stream past.
Edge cases
- Fewer than k values so far:
None, so callers cannot mistake a missing answer for a number. - k = 1 is just a running minimum; k larger than the stream never produces a value.
- Duplicates count separately, as the trace shows.
- k below 1 raises
ValueError.
Common mistakes
- Using a min-heap of size k for the kth smallest. A min-heap of size k tracks the kth largest; for kth smallest the top must be the biggest of the kept values, so it is a max-heap.
- Pushing every value and never evicting, which makes the heap O(n) in size and the top is the overall minimum, not the kth.
- Forgetting the negation when comparing: the test is
x < -heap[0].
When two heaps are needed
A single heap works because k is fixed. If k changes between queries (the median is the case where k moves with the count), the boundary has to move, which is why the median uses two heaps, one for each side of the boundary.
Running the code
python3 kth_smallest_stream.py
Python 3.12, standard library only.
Unlock Full Question Bank
Get access to all 15 Heaps and Priority Queues interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.