--- title: 'Two Heaps' source: 'https://academia.sh/en/courses/advanced-algorithms/two-heaps' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:30+00:00' license: 'CC BY-SA 4.0' --- # Two Heaps Median tracking in a stream; how removing the rebalancing step corrupts 295 of 480 medians, and how the pattern's gain grows as the stream lengthens. The previous five patterns held the entire input in hand: the array could be seen start to end, revisited at any position. This lesson's pattern loses that ability. Values **flow one at a time**, and after every new value a question must be answered: what is the **median** of what has been seen so far. The direct way to find the median is to keep a sorted list: insert every new value at the right place and read the middle. The pattern instead keeps **two heaps**: the lower half in a **max-heap**, the upper half in a **min-heap**. The median is read from the tops of the two heaps. The heap invariant, the sift operations, and the array representation were established in the Data Structures course's Heaps lesson; they are **not repeated** here, they are used directly. The pattern's precondition is that the two heaps stay **balanced**. This lesson breaks that balance and counts how many medians turn out wrong. ## Pattern and the Balance Precondition Every new value is placed first: if it is not greater than the low half's top, it goes to the max-heap; otherwise it goes to the min-heap. That alone is not enough, because values can pile up on one side. The second step is the **rebalancing step**: whenever the heaps' sizes differ by more than one, the top of the larger one is moved to the other. The median can only be read once the two heaps' sizes are correct. If the total is odd, the top of the larger heap is the median; if even, the average of the two tops. If the balance is off, both rules point to the wrong place — the pattern still returns a number. **PP40.** The corpus is 40 streams; each stream carries 12 values, ranging from −9 to 20. Seed `20260218`. Every stream asks for a median after every value; **480** questions total. **PP41.** The oracle inserts every value into a sorted list by **linear scan** and reads the middle. Every comparison is counted as one step. **PP42.** The pattern's step count is the heap operations' **real comparisons**; values are placed in a wrapper that counts comparisons, the step count is not estimated. **PP43.** The only thing that breaks the precondition is **removing the rebalancing step**. The value-placement rule, the median-reading rule, the corpus, and the seed are the same. ```python import heapq SEED, LENGTH, CORPUS_SIZE = 20260218, 12, 40 def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def stream_corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH): r = generator(seed) return [{"no": i + 1, "stream": [r(30) - 9 for _ in range(length)]} for i in range(n)] class Counter: def __init__(self): self.step = 0 def count(self, n=1): self.step += n class Counted: """Wraps a value and counts every heap comparison. sign=-1 gives a max-heap.""" __slots__ = ("d", "sign", "s") def __init__(self, d, sign, s): self.d, self.sign, self.s = d, sign, s def __lt__(self, o): self.s.count() return self.d * self.sign < o.d * o.sign def oracle_median(stream, s): """Inserts every value into a sorted list by linear scan, reads the middle.""" sorted_list, answer = [], [] for x in stream: i = 0 while i < len(sorted_list): s.count() if sorted_list[i] >= x: break i += 1 sorted_list.insert(i, x) n = len(sorted_list) answer.append(sorted_list[n // 2] if n % 2 else (sorted_list[n // 2 - 1] + sorted_list[n // 2]) / 2) return answer def pattern_two_heaps(stream, rebalance, s): """PRECONDITION: the two heaps must stay balanced. low=max-heap, high=min-heap.""" low, high, answer = [], [], [] max_diff = 0 for x in stream: if not low or x <= low[0].d: heapq.heappush(low, Counted(x, -1, s)) else: heapq.heappush(high, Counted(x, 1, s)) if rebalance: if len(low) > len(high) + 1: heapq.heappush(high, Counted(heapq.heappop(low).d, 1, s)) elif len(high) > len(low): heapq.heappush(low, Counted(heapq.heappop(high).d, -1, s)) max_diff = max(max_diff, abs(len(low) - len(high))) if not low: answer.append(high[0].d) elif not high or len(low) > len(high): answer.append(low[0].d) elif len(high) > len(low): answer.append(high[0].d) else: answer.append((low[0].d + high[0].d) / 2) return answer, max_diff K = stream_corpus() print("corpus:", len(K), "streams x", LENGTH, "values =", len(K) * LENGTH, "medians") print("setup wrong medians diverging streams/40 pattern oracle ratio max diff") for ad, rebalance in (("balanced ", True), ("unbalanced", False)): wrong, diverging, pk, ok, diff = 0, 0, 0, 0, 0 for k in K: s1, s2 = Counter(), Counter() a, f = pattern_two_heaps(k["stream"], rebalance, s1) b = oracle_median(k["stream"], s2) pk, ok = pk + s1.step, ok + s2.step diff = max(diff, f) broken = sum(1 for x, y in zip(a, b) if x != y) wrong += broken diverging += broken > 0 print(f"{ad} {wrong:14d} {diverging:15d} {pk:5d} {ok:5d} {ok / pk:5.2f}" f" {diff:13d}") ``` ``` corpus: 40 streams x 12 values = 480 medians setup wrong medians diverging streams/40 pattern oracle ratio max diff balanced 0 0 1261 1693 1.34 1 unbalanced 295 39 550 1693 3.08 12 ``` In the balanced setup, **480 of 480 medians** match the oracle; the largest size difference is **1**, that is, the balance never breaks. Once the rebalancing step is removed, **295 medians** come out wrong and **39 of 40** streams are corrupted. The second row's step column carries the lesson's central conflict: the unbalanced pattern spends **550** steps, **less than half** the balanced one. The rebalancing step makes up the larger share of the pattern's total work; removing it speeds the pattern up against the oracle from a ratio of 1.34 to **3.08**. The fastest setup is again the most broken one. The largest size difference also climbs from 1 to **12**: every value piles into a single heap. ## How Imbalance Produces a Wrong Median Without the rebalancing step, the placement rule feeds on itself. When a small value arrives, it goes into the low half; the low half's top does not shrink further, but the half grows. The next value is compared against the top of that grown half and mostly lands there too. One heap swells while the other stays empty, and the median-reading rule keeps looking at the **same** top. ```python import heapq def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def stream_corpus(seed, n=40, length=12): r = generator(seed) return [[r(30) - 9 for _ in range(length)] for _ in range(n)] def oracle_median(stream): sorted_list, answer = [], [] for x in stream: i = 0 while i < len(sorted_list) and sorted_list[i] < x: i += 1 sorted_list.insert(i, x) n = len(sorted_list) answer.append(sorted_list[n // 2] if n % 2 else (sorted_list[n // 2 - 1] + sorted_list[n // 2]) / 2) return answer def pattern_two_heaps(stream, rebalance): """low=max-heap (sign flipped), high=min-heap.""" low, high, answer = [], [], [] for x in stream: if not low or x <= -low[0]: heapq.heappush(low, -x) else: heapq.heappush(high, x) if rebalance: if len(low) > len(high) + 1: heapq.heappush(high, -heapq.heappop(low)) elif len(high) > len(low): heapq.heappush(low, -heapq.heappop(high)) if not low: answer.append(high[0]) elif not high or len(low) > len(high): answer.append(-low[0]) elif len(high) > len(low): answer.append(high[0]) else: answer.append((-low[0] + high[0]) / 2) return answer first = stream_corpus(20260218)[0] print("stream 1 :", first) print(" oracle :", oracle_median(first)) print(" balanced :", pattern_two_heaps(first, True)) print(" unbalanced:", pattern_two_heaps(first, False)) print() print("seed setup wrong medians/480 diverging streams/40 first wrong position") for seed in (20260218, 20260219): K = stream_corpus(seed) for ad, rebalance in (("balanced ", True), ("unbalanced", False)): wrong, diverging, first_position = 0, 0, [] for stream in K: a, b = pattern_two_heaps(stream, rebalance), oracle_median(stream) broken = [i + 1 for i, (x, y) in enumerate(zip(a, b)) if x != y] wrong += len(broken) diverging += bool(broken) if broken: first_position.append(broken[0]) average = round(sum(first_position) / len(first_position), 2) if first_position else 0 print(f"{seed} {ad} {wrong:18d} {diverging:15d} {average:16}") ``` ``` stream 1 : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1] oracle : [-8, -6.5, -5, -3.0, -1, 0.5, 2, 1.5, 2, 2.0, 2, 2.0] balanced : [-8, -6.5, -5, -3.0, -1, 0.5, 2, 1.5, 2, 2.0, 2, 2.0] unbalanced: [-8, -6.5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5] seed setup wrong medians/480 diverging streams/40 first wrong position 20260218 balanced 0 0 0 20260218 unbalanced 295 39 3.44 20260219 balanced 0 0 0 20260219 unbalanced 268 38 3.89 ``` The first stream's trace shows the mechanism in one line. The balanced setup produces every one of the oracle's answers. The unbalanced setup gives the first three medians correctly, then **locks onto −5** and writes the same number for the rest of the stream. Even as the values climb to 16 and 17, the answer never changes, because every large value has piled into a single heap and the top being read has stayed fixed. **PP44.** The second corpus comes from seed `20260219`. Wrong medians are **268/480**, versus **295/480** in the first; diverging streams are **38/40** and **39/40**. Ratios fall between 0.56 and 0.61, the same order of magnitude — the result does not depend on the corpus. **PP45.** The first wrong median arrives on average at the **3.44th** value. The balance breaks by at latest the fourth value, meaning the defect forms not at the stream's end but at its **start**. This last number explains not why the defect goes unnoticed but why it **can**. The first three answers are correct; a short test stream that checks only these three sees nothing. The defect only accumulates as the stream lengthens, and no single wrong median can be picked out by looking at the output — the unbalanced pattern still returns a plausible number. ## The Pattern's Gain Grows With Stream Length On a twelve-value stream, the balanced pattern's ratio is **1.34**. That is too small a gain to be worth building the pattern for, and it raises a question: what is the point of two heaps. The answer lies in stream length. The oracle's every insertion scans half the list, so its cost is directly proportional to the value count seen so far; a heap insertion instead makes as many comparisons as the heap's **depth**. **PP46.** In this measurement stream count drops to 10 and stream length climbs from 12 to 200. The corpus comes from the same generator, the same seed; the only thing that changes is length. ```python import heapq def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def stream_corpus(seed, n, length): r = generator(seed) return [[r(30) - 9 for _ in range(length)] for _ in range(n)] class Counter: def __init__(self): self.step = 0 def count(self, n=1): self.step += n class Counted: """Counts every heap comparison. sign=-1 gives a max-heap.""" __slots__ = ("d", "sign", "s") def __init__(self, d, sign, s): self.d, self.sign, self.s = d, sign, s def __lt__(self, o): self.s.count() return self.d * self.sign < o.d * o.sign def oracle_median(stream, s): sorted_list, answer = [], [] for x in stream: i = 0 while i < len(sorted_list): s.count() if sorted_list[i] >= x: break i += 1 sorted_list.insert(i, x) n = len(sorted_list) answer.append(sorted_list[n // 2] if n % 2 else (sorted_list[n // 2 - 1] + sorted_list[n // 2]) / 2) return answer def pattern_two_heaps(stream, s): low, high, answer = [], [], [] for x in stream: if not low or x <= low[0].d: heapq.heappush(low, Counted(x, -1, s)) else: heapq.heappush(high, Counted(x, 1, s)) if len(low) > len(high) + 1: heapq.heappush(high, Counted(heapq.heappop(low).d, 1, s)) elif len(high) > len(low): heapq.heappush(low, Counted(heapq.heappop(high).d, -1, s)) answer.append(low[0].d if len(low) > len(high) else (low[0].d + high[0].d) / 2) return answer print("stream length diverging streams/10 pattern oracle ratio") for length in (12, 25, 50, 100, 200): K = stream_corpus(20260218, 10, length) diverging, pk, ok = 0, 0, 0 for stream in K: s1, s2 = Counter(), Counter() a = pattern_two_heaps(stream, s1) b = oracle_median(stream, s2) pk, ok = pk + s1.step, ok + s2.step diverging += (a != b) print(f"{length:13d} {diverging:15d} {pk:5d} {ok:6d} {ok / pk:6.2f}") ``` ``` stream length diverging streams/10 pattern oracle ratio 12 0 303 431 1.42 25 0 949 1602 1.69 50 0 2471 6440 2.61 100 0 5971 25292 4.24 200 0 13686 98651 7.21 ``` Diverging streams are **zero** at all five lengths: as long as balance is preserved, the pattern is correct regardless of length. The ratio climbs from 1.42 to **7.21**. The oracle's step count grows from 431 to 98,651, that is, **229 times**, while the pattern's step count grows from 303 to 13,686, **45 times**. This column is the reason for building the pattern. Keeping two heaps for a twelve-value stream is unnecessary; for a two-hundred-value stream it pays off seven times over, and it pays off more on longer streams still. **A pattern's gain is not a number, it is a trend**, and measuring it at a single input size reads it wrong. ## Three Numbers | Metric | Oracle | Pattern | Diverging input | |---|---|---|---| | Balanced, 12-value stream | 1693 steps | 1261 steps | **0/480 medians** | | Unbalanced, 12-value stream | 1693 steps | 550 steps | **295/480 medians** | | Balanced, 200-value stream | 98,651 steps | 13,686 steps | **0/10 streams** | The only difference between the first and second row is a two-line rebalancing step; those two lines spend more than half the pattern's steps and prevent **295 wrong answers**. The third row shows why that cost is paid. The diverging-input column of the table carries two separate units, and this must be noted. In the first two rows the unit is a **median**, because in a data stream every value produces a question and what needs measuring is how many questions were answered wrongly. In the third row the unit is a **stream**, because there the question asked is whether the pattern breaks with length. Mixing the two units makes the ratios impossible to compare: 295/480 and 0/10 cannot be read on the same scale. Every pattern that measures streaming data must state this distinction explicitly. ## Summary - The two heaps pattern gives the median of a data stream by holding the lower half in a max-heap and the upper half in a min-heap, and reads two heap tops. - The precondition is that the two heaps stay balanced; once the rebalancing step is removed, **295 of 480** medians come out wrong and 39 of 40 streams are corrupted. - The rebalancing step spends more than half the pattern's total steps: without it the pattern spends 550 steps instead of 1261, and the ratio climbs from 1.34 to 3.08. - The first wrong median arrives on average at the 3.44th value; the defect forms at the stream's start but stays invisible in a short test because the first few answers are correct. - The pattern's gain grows with stream length: the ratio is 1.42 at 12 values, 7.21 at 200, and diverging streams are zero at every length. ## Next Step Two heaps gave the median, that is, the **middle value in sorted order**. The median is a special case; the general question is what the **k-th** value is in sorted order. The next lesson answers this question with two separate patterns — a k-sized heap and partitioning — and tests both against the same oracle. There the precondition touches not the data but the **question itself**: in duplicate values, "the k-th element" and "the k-th distinct value" are not the same thing, and that difference will be counted.