Two Heaps

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.

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.

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.

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.