Two Heaps and Running Median

One heap gives you the extreme of a collection in $O(1)$. Sometimes you need the middle instead — and a heap cannot give you that, because the middle is exactly the element a heap makes no promises about.

The trick is to stop asking one heap for the middle and instead split the data in half:

• a max-heap holding the smaller half, so its top is the largest of the small values;
• a min-heap holding the larger half, so its top is the smallest of the large values.

Those two tops sit either side of the median. Keep the halves balanced in size and the median is always readable in $O(1)$, with $O(\log n)$ inserts.

What you’ll learn

• Python has no max-heap — the negation trick, and where it bites.
• The push-then-shift insert that keeps both heaps correctly ordered without any comparison logic.
• The balance invariant, and why “differ by at most one” is not quite enough.
• The second use of two heaps: one heap sorted by availability, another by value — which is what LC 502 actually needs.
• Three real LeetCode problems solved in the browser: 295, 502, 1962.

The cue

You are looking at two heaps when…

• You need a median of data that keeps arriving — 295, 480.
• You need the middle, a percentile, or to keep two groups balanced.
• Items become available under one ordering but should be chosen under another — 502 IPO, 2542. One heap for “what is unlocked”, one for “what is best”.
• A single heap almost works, but you also need to undo or re-insert modified elements — 1962.

The anti-cue: if you only need the kth largest, one heap or quickselect is simpler. Two heaps earn their complexity when you need the boundary between two halves.

Python has no max-heap

heapq is a min-heap only. To get a max-heap, push negated values and negate again on the way out:

python

import heapq
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
largest = -max_heap[0]          # 5

Two places this bites:

1. Forgetting to negate on read. max_heap[0] is -5, not 5.
2. Tuples. Negating (-count, name) flips the count ordering but also flips name, which is usually not what you want. Negate only the field you mean to reverse — see Sorting with Custom Comparators.

Visual intuition

The running median needs one thing from each half: the largest of the small half and the smallest of the large half. A heap gives exactly that in $O(1)$, and the sift operation is what maintains it:

heapA heap only ever promises you its root — which is all the median needsO(log n) insert, O(1) peek

as a tree

heap is empty

as an array — the real thing

size0

1def push(heap, value):2    heap.append(value)              # always a valid TREE shape3    i = len(heap) - 14    while i > 0:5        p = (i - 1) // 26        if heap[p] <= heap[i]: break    # heap property restored7        heap[i], heap[p] = heap[p], heap[i]8        i = p

setupA min-heap keeps one promise only: every parent is ≤ its children. It says nothing about siblings, and nothing about left-to-right order — which is why a heap is not sorted and cannot answer "is x present" quickly.

Play‹›1/16⟲

Watch how little work an insert does: one path from the new leaf to the root, not a re-sort. That is why two heaps beat a sorted list here -- a sorted insert is O(n) shifting, while two heap pushes plus a rebalance are O(log n) and the two roots straddle the median.

The template — running median

The elegant part of this insert is that it needs no comparison to decide which heap a new value belongs in. Always push into low, then immediately move low’s maximum across to high. That guarantees every value in low is ≤ every value in high, whatever order things arrive in.

median_finder.py

import heapq
 
 
class MedianFinder:
    def __init__(self):
        self.low = []      # max-heap (negated): the smaller half
        self.high = []     # min-heap: the larger half
        # invariant: len(low) == len(high)  or  len(low) == len(high) + 1
 
    def add_num(self, num):
        # 1. always push into low, 2. shift low's max into high
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        # 3. rebalance so low is never smaller than high
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
 
    def find_median(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])                  # odd count
        return (-self.low[0] + self.high[0]) / 2.0      # even count
 
 
mf = MedianFinder()
for x in [1, 2, 3, 4]:
    mf.add_num(x)
print(mf.find_median())    # 2.5

Why push-then-shift beats “compare and choose”

The obvious insert is “if num <= low[0], put it in low, otherwise put it in high”, then rebalance. That works, but it needs a guard for the empty-heap case and it is easy to get the comparison boundary wrong.

Push-then-shift is unconditional. Pushing into low then moving low’s maximum to high cannot violate the ordering: the element that ends up in high is the largest of low ∪ {num}, so everything remaining in low is below it. Three lines, no branches, no empty-heap special case.

Keeping low the one allowed to be larger makes find_median simpler too: for an odd count the median is always -low[0].

Dry run

Ten values arriving in a deliberately awkward order: 5, 15, 1, 3, 2, 8, 7, 9, 10, 6. Both heaps are printed as the sorted halves they represent — low descending, high ascending — so the invariant max(low) <= min(high) is readable at a glance. The real low is a negated min-heap and its internal array order is not sorted.

Call	low (larger half of the smaller values, descending)	high (ascending)	Rebalanced?	Median
add(5)	[5]	[]	yes	5.0
add(15)	[5]	[15]	no	10.0
add(1)	[5, 1]	[15]	yes	5.0
add(3)	[3, 1]	[5, 15]	no	4.0
add(2)	[3, 2, 1]	[5, 15]	yes	3.0
add(8)	[3, 2, 1]	[5, 8, 15]	no	4.0
add(7)	[5, 3, 2, 1]	[7, 8, 15]	yes	5.0
add(9)	[5, 3, 2, 1]	[7, 8, 9, 15]	no	6.0
add(10)	[7, 5, 3, 2, 1]	[8, 9, 10, 15]	yes	7.0
add(6)	[6, 5, 3, 2, 1]	[7, 8, 9, 10, 15]	no	6.5

Every median matches statistics.median on the corresponding prefix — [5.0, 10.0, 5.0, 4.0, 3.0, 4.0, 5.0, 6.0, 7.0, 6.5] from both.

Four things the trace makes concrete:

add(5) on empty heaps needs no special case. Push -5 into low, immediately move it to high (so low is empty and high is [5]), then the rebalance sees len(high) > len(low) and moves it straight back. Net effect: low = [5], high = []. Three unconditional lines handled the empty case that a compare-and-choose insert would need a guard for.

Rebalancing fires on exactly the odd-numbered inserts. Rows 1, 3, 5, 7, 9 — every time the count becomes odd, because push-then-shift always leaves high one ahead and the rebalance pulls it back. On even inserts the shift lands the sizes equal and nothing moves. That regularity is worth noticing: it means the “extra” element always ends up in low, which is why find_median can return -low[0] for the odd case with no further checks.

add(7) is the row that proves the invariant is maintained. Before it, low = [3, 2, 1] and high = [5, 8, 15]. The new value 7 belongs in the upper half, and the code pushes it into low anyway. That is momentarily wrong — and then the shift moves low’s maximum, which is now 7 itself, straight into high. The rebalance then pulls high’s minimum, 5, down into low. Result: low = [5, 3, 2, 1], high = [7, 8, 15], correctly partitioned. The value never had to be compared against anything. The heap’s own ordering decided where it ended up.

add(15) shows why the median can be a value that never was one. After two elements the answer is (5 + 15) / 2 = 10.0, which is not in the stream at all. Returning an int here, or reaching for low[0] alone, is the standard bug — the even case needs both tops and a float division.

The low[0] sign trap

low is a max-heap simulated by negating on the way in, so its top is -low[0], not low[0]. In the final state low’s internal array begins with -6, and the median calculation (-low[0] + high[0]) / 2.0 reads (6 + 7) / 2.0 = 6.5. Drop one negation and the numbers stay plausible while every answer is wrong — and the shift line negates twice (heappush(high, -heappop(low))), which is where a missing sign is easiest to overlook.

Complexity

Operation	Two heaps	Sorted list (bisect.insort)	Re-sort each query
Insert	$O(\log n)$	$O(n)$ (shifting)	$O(1)$
Find median	$O(1)$	$O(1)$	$O(n \log n)$
$n$ inserts + queries	$O(n \log n)$	$O(n^2)$	$O(n^2 \log n)$

bisect.insort keeps a sorted list and reads the median in $O(1)$, but each insert shifts $O(n)$ elements. It is genuinely competitive for small n because the shifting is a fast memmove — worth mentioning, but the two-heap answer is what the $O(\log n)$ requirement is asking for.

The variant map

Variant	The two heaps hold	Canonical problem
Running median	Smaller half (max-heap) / larger half (min-heap)	295 Find Median from Data Stream
Median over a window	Same, plus lazy deletion of expired values	480 Sliding Window Median
Unlock then choose	Sorted by cost/availability / by value	502 IPO · 2542
Modify and re-insert	One heap suffices, but items return changed	1962 Remove Stones
Balance two groups	The two groups themselves	Scheduling / load-balancing variants

LC 480 and the lazy-deletion trick

A sliding-window median needs to remove the value leaving the window — and a heap cannot remove an arbitrary element. The standard fix is lazy deletion: keep a Counter of values that ought to be gone, and whenever a heap top appears in it, pop and discard instead of using it. Balance is tracked with explicit size counters rather than len(), since the heaps now contain garbage.

It is fiddly. In Python, sortedcontainers.SortedList solves LC 480 far more cleanly in $O(n \log k)$ — but it is not in the standard library, so know the lazy-deletion approach for interviews where imports are restricted.

Practice — real LeetCode problems

LC 295 — Find Median from Data Stream · Hard

Problem. Implement MedianFinder with addNum(num) and findMedian(). The median of an even-length collection is the mean of the two middle values.

Constraints. -10^5 <= num <= 10^5, up to 5 * 10^4 calls, findMedian is only called after at least one addNum.

Example. Add 1, add 2, findMedian() gives 1.5; add 3, findMedian() gives 2.0.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Split the data into a smaller half and a larger half. The median is then determined entirely by the two heap tops — the largest small value and the smallest large value.

Time $O(\log n)$ per addNum, $O(1)$ per findMedian. Space $O(n)$.

Two invariants do all the work:

1. Ordering: every value in low is ≤ every value in high. The push-then-shift insert maintains this without comparing anything.
2. Balance: len(low) equals len(high) or exceeds it by exactly one. Allowing only low to be the larger one makes the odd case unambiguous.

Note float(-self.low[0]) in the odd branch: LeetCode expects a float, and returning a bare int can fail strict comparisons. The even branch divides with / so it is already a float.

Follow-ups you should expect:

• “What if 99% of numbers are in a small range?” LeetCode asks this directly. If values are bounded integers, counting sort over the range gives $O(1)$ insert and $O(\text{range})$ median — or a Fenwick tree over the value range for $O(\log \text{range})$ both ways.
• “Sliding window median (LC 480)?” Add lazy deletion, or use SortedList.
• “Track an arbitrary percentile?” Same structure, but the balance ratio becomes p : 1-p instead of 1 : 1.
• “Remove a number too?” Heaps cannot delete arbitrary elements — lazy deletion with a Counter, or switch to a balanced BST / SortedList.

LC 502 — IPO · Hard

Problem. You can complete at most k projects. Project i requires capital[i] capital to start and yields profits[i], which is added to your capital. Starting with w capital, maximise your final capital.

Constraints. 1 <= k <= 10^5, 0 <= w <= 10^9, 1 <= len(profits) <= 10^5, 0 <= profits[i] <= 10^4, 0 <= capital[i] <= 10^9.

Examples. k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] gives 4 · k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] gives 6

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Two different orderings are in play, and conflating them is the trap:

• Availability is by capital required — you unlock cheapest-first.
• Desirability is by profit — you always want the best available one.

Sorting handles the first (a pointer sweeps forward and never goes back, since capital only grows). A max-heap handles the second.

Time $O(n \log n)$ for the sort plus $O((n + k) \log n)$ for the heap operations. Space $O(n)$.

Why greedy is correct: capital never decreases, so a project affordable now stays affordable. Taking the largest available profit therefore cannot reduce your future options — it can only enlarge them. There is no reason to save a project for later.

Two details worth stating:

• break when nothing is available. Not merely an optimisation: if w is below the cheapest requirement, no further profit can arrive, so continuing would loop k times doing nothing. (1, 0, [1,2,3], [1,1,2]) returns 0 for exactly this reason — nothing is affordable at w = 0.
• k may exceed the project count. The break handles that too, which the fourth case (k = 10, three projects) checks.

The “unlock by one key, choose by another” shape is the transferable idea. It reappears in task scheduling, meeting rooms with priorities, and LC 2542.

Follow-ups you should expect: “Why is greedy safe?” — the argument above; be ready to state it. “What if profits could be negative?” — greedy breaks, since taking one could lock you out later. “What if capital were consumed rather than just required?” — a genuinely different (knapsack-like) problem. “Minimise the number of projects to reach a target?” — same structure, invert the loop condition.

LC 1962 — Remove Stones to Minimize the Total · Medium

Problem. Given piles, where piles[i] is a number of stones, you may apply this operation k times: choose a pile and remove floor(piles[i] / 2) stones from it. Return the minimum total number of stones remaining. (You may pick the same pile more than once.)

Constraints. 1 <= len(piles) <= 10^5, 1 <= piles[i] <= 10^4, 1 <= k <= 10^5.

Examples. piles = [5,4,9], k = 2 gives 12 · piles = [4,3,6,7], k = 3 gives 12

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Removing floor(p / 2) from a pile of size p removes more stones the larger p is, so each operation should always target the current maximum. Crucially the pile does not disappear — it returns at size p - floor(p/2) = ceil(p/2) and may well still be the largest, so it must go back into the heap.

Time $O(n + k \log n)$. Space $O(n)$.

Three Python details that matter here:

• heapify is $O(n)$, cheaper than n individual pushes at $O(n \log n)$.
• heapreplace is one operation, not a heappop followed by a heappush — it sifts once instead of twice.
• largest - largest // 2 avoids any rounding ambiguity. Writing ceil(largest / 2) goes through a float, which is unnecessary and imprecise for large values.

The largest <= 1 early exit matters for correctness of the loop’s intent as well as speed: 1 - 1 // 2 == 1, so once every pile is 1, further operations change nothing and the loop would spin k times pointlessly. ([1,1,1], 5) returning 3 is that case.

Note this problem needs only one heap — it is included here because it completes the family: the two-heap problems are the ones where a single ordering is insufficient, and seeing where one heap does suffice sharpens the distinction.

Follow-ups you should expect: “Why is greedy optimal?” — the gain from halving is monotonic in pile size, and operations are independent across piles, so an exchange argument shows always taking the largest is at least as good. “What if the operation removed a fixed amount instead?” — greedy still works but piles can empty. “What if you could only use each pile once?” — then sort descending and take the top k; no heap needed.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 2542 is LC 502’s shape in disguise

Maximum Subsequence Score asks you to pick k indices maximising sum(nums1 chosen) * min(nums2 chosen). Sort the pairs by nums2 descending; then as you sweep, the current element’s nums2 is the minimum for any subset drawn from the prefix so far. Keep a min-heap of the nums1 values to hold the best k seen, evicting the smallest.

Same two-ordering idea as IPO: one ordering fixes a constraint (the minimum), the other optimises within it.

5 problems

0 easy2 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○1962Remove Stones to Minimize the TotalmediumHalved piles return to the heap; `heapify` + `heapreplace`
• ○2542Maximum Subsequence ScoremediumSort by the multiplier descending, keep a min-heap of the top `k` of the other array
• ○295Find Median from Data StreamhardThe base two-heap balanceNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetabloomberg
• ○480Sliding Window MedianhardTwo heaps **plus lazy deletion** of expired values
• ○502IPOhardUnlock by capital, choose by profitLeetCode Top Interview 150

Interview follow-ups

They ask	What they’re checking	The answer
“Why can’t one heap give you the median?”	Understanding the structure	A heap only orders along root-to-leaf paths; the middle element has no guaranteed position
“How do you get a max-heap in Python?”	Language fluency	Negate on push and on read; with tuples, negate only the field you mean to reverse
“Why push-then-shift?”	Depth	It maintains the ordering unconditionally — no comparison and no empty-heap guard
“Why let low be the larger half?”	Precision	It makes the odd-count median unambiguously -low[0], with no extra branch
“Sliding window median?”	Knowing the hard part	Heaps cannot delete arbitrary elements: lazy deletion with a Counter plus explicit size tracking, or SortedList
“Values are in a small range?”	Alternative structures	Counting sort or a Fenwick tree over the value range beats heaps outright
“Why is IPO’s greedy correct?”	Rigour	Capital never decreases, so anything affordable now stays affordable — taking the best available can never reduce future options

Edge-case checklist

• First insert — findMedian after one addNum must work; push-then- shift handles the empty heap without a guard.
• Odd vs even counts — one returns a single value, the other a mean; test both, alternating.
• Return type — float(-low[0]) for the odd case, since an int can fail strict comparison.
• Duplicate values — perfectly fine; they distribute across both heaps.
• All identical — the median equals that value; balance still holds.
• Negative values — easy to break with the negation trick; test them.
• Nothing affordable (LC 502) — must break, not loop k times.
• k larger than the input (LC 502, 1962) — the early exit covers it.
• Piles already all 1 (LC 1962) — halving removes nothing; exit early.

Self-check

pch.quizTag pch.quizDefaultTitle

1. `add_num` always pushes into `low` first, even when the value clearly belongs in the upper half. Why is that correct?

   A It is not -- it works only because of the rebalance step B The next line moves `low`'s maximum into `high`, and that maximum is the largest of `low` plus the new value, so everything left in `low` stays below it C Because `low` is a max-heap, pushing a large value is a no-op D It relies on the values arriving in sorted order
   pch.quizShowAnswer

   B — The next line moves `low`'s maximum into `high`, and that maximum is the largest of `low` plus the new value, so everything left in `low` stays below it — Push-then-shift is unconditional and cannot violate the ordering. In the trace, add(7) pushes 7 into `low` when it belongs in the upper half; the shift immediately moves 7 -- now `low`'s maximum -- into `high`, and the rebalance pulls 5 back down. The value was never compared against anything; the heap's own ordering placed it.

2. Why is push-then-shift preferred over "if num <= low[0] push to low, else push to high"?

   A It is faster -- one heap operation instead of two B It is unconditional: no empty-heap guard and no comparison boundary to get wrong C Compare-and-choose breaks when there are duplicate values D It keeps both heaps exactly the same size
   pch.quizShowAnswer

   B — It is unconditional: no empty-heap guard and no comparison boundary to get wrong — Compare-and-choose is correct but needs a guard for the first insert (there is no low[0] yet) and puts a `<=` boundary where an off-by-one is easy. Push-then-shift is three straight-line operations that handle the empty case for free -- in the trace, add(5) on two empty heaps works with no special casing at all. It costs an extra heap operation; the trade is fewer branches to get wrong under pressure.

3. The invariant allows `len(low) == len(high) + 1` but not the reverse. What does that buy?

   A It halves the memory used by `high` B For an odd count the median is always `-low[0]`, with no branch to decide which heap holds it C It makes the rebalance step unnecessary D It guarantees the heaps stay balanced without counters
   pch.quizShowAnswer

   B — For an odd count the median is always `-low[0]`, with no branch to decide which heap holds it — Fixing which side may be larger removes a decision from `find_median`. In the trace, the rebalance fires on exactly the odd-numbered inserts -- rows 1, 3, 5, 7, 9 -- so the extra element always lands in `low`. Allowing either side to be larger would work too, but every median read would need to check which.

4. After adding 5 and 15, `find_median()` returns 10.0. What does that illustrate?

   A A bug -- the median of two elements should be one of them B The even case averages both heap tops, so the answer need not be a value from the stream, and it needs float division C That the heaps are unbalanced D That 15 was pushed into the wrong heap
   pch.quizShowAnswer

   B — The even case averages both heap tops, so the answer need not be a value from the stream, and it needs float division — The median of an even-sized set is the mean of the two middle values, and 10.0 is in neither heap nor the input. The standard bugs both live here: returning `-low[0]` alone (giving 5), or using integer division so a result like 6.5 silently truncates to 6.

5. `low` is a max-heap built by negating values. Where is a missing negation easiest to miss?

   A In `find_median`, where the sign is obvious from context B In the shift line `heappush(high, -heappop(low))`, which negates twice in one expression C In the rebalance condition comparing lengths D In `__init__`, where the heaps are created
   pch.quizShowAnswer

   B — In the shift line `heappush(high, -heappop(low))`, which negates twice in one expression — That line pops a negated value and re-negates it to store a positive one in `high`. Drop either sign and the values stay plausible-looking while every subsequent median is wrong -- no crash, no exception. The length comparison carries no sign at all, and `find_median`'s negation is right next to the return value where it is easier to spot.

6. LC 480 asks for the median over a sliding window. Why can this template not be used unchanged?

   A The heaps grow too large for the memory limit B A value leaving the window must be removed, and a heap cannot delete an arbitrary element C The median of a window is not well defined for even window sizes D Heaps cannot hold duplicate values
   pch.quizShowAnswer

   B — A value leaving the window must be removed, and a heap cannot delete an arbitrary element — `heapq` only removes the top. The standard fix is lazy deletion: keep a Counter of values that ought to be gone, and whenever a heap top appears in it, pop and discard rather than use it. Balance then has to be tracked with explicit size counters, since len() now counts garbage. In Python, sortedcontainers.SortedList solves it far more cleanly -- but it is not in the standard library, so know the lazy version for restricted-import interviews.

7. For a stream of n values with a median query after each, why not keep a sorted list with `bisect.insort`?

   A Because bisect.insort is O(log n) but reading the median is O(n) B Insertion shifts O(n) elements, so n inserts are O(n^2) -- though the shift is a fast memmove, which makes it genuinely competitive for small n C Because a sorted list cannot hold duplicates D Because the median of a sorted list requires a linear scan
   pch.quizShowAnswer

   B — Insertion shifts O(n) elements, so n inserts are O(n^2) -- though the shift is a fast memmove, which makes it genuinely competitive for small n — The binary search to find the position is O(log n); the insertion itself shifts memory and is O(n). Total O(n^2) against the two-heap O(n log n). Worth saying out loud that the constant factor is small enough for the sorted list to win at small n -- but an explicit O(log n)-per-insert requirement in the problem statement is asking for the two-heap answer.

Recall card

• Two heaps split a stream at the median: low is a max-heap of the smaller half, high a min-heap of the larger. Invariant max(low) <= min(high).
• Insert is push-then-shift, unconditional: push into low, move low’s max into high, then pull back if high is longer. No comparison, no empty-heap guard, no branches.
• Keep the size skew on one side (len(low) == len(high) + 1 at most). Then the odd-count median is always -low[0] with no branch.
• Rebalance fires on odd inserts only — the extra element always lands in low.
• low is negated. Its top is -low[0], and the shift line negates twice. A missing sign gives plausible wrong answers, never a crash.
• The even case is (-low[0] + high[0]) / 2.0 — both tops, float division. The answer need not be a value from the stream.
• $O(\log n)$ insert, $O(1)$ median. A bisect.insort sorted list is $O(n)$ per insert but has a tiny constant — competitive at small n, and worth naming as the alternative.
• Sliding-window median (LC 480) needs lazy deletion: a Counter of doomed values, discard them when they surface, and track balance with explicit counters. SortedList is cleaner when imports are allowed.

Recap

• One heap gives you an extreme; two heaps give you the boundary between two halves, which is what a median is.
• max-heap of the smaller half + min-heap of the larger half. The two tops straddle the median, so reading it is $O(1)$ and inserting is $O(\log n)$.
• Push-then-shift: push into low, move low’s max into high, then rebalance. Unconditional, no comparisons, no empty-heap case.
• Let low be the half allowed to be bigger, so the odd-count median is always -low[0].
• Python has no max-heap — negate, and be careful with tuples.
• The second two-heap shape is unlock by one ordering, choose by another (LC 502): sort by availability, heap by value.
• Removing an arbitrary element needs lazy deletion (LC 480), or a different structure entirely.

Next: K-way Merge — using a heap to merge many sorted sequences at once.