python 35 lines · 8 steps

Running median with two heaps

A pair of complementary heaps keeps the median available in constant time as values stream in.

Explained by highlit
Advanced heaps streaming invariants data-structures generators
1import heapq
2 
3 
4class MovingMedian:
5 def __init__(self):
6 self._low = []
7 self._high = []
8 
9 def add(self, value):
10 if not self._low or value <= -self._low[0]:
11 heapq.heappush(self._low, -value)
12 else:
13 heapq.heappush(self._high, value)
14 self._rebalance()
15 
16 def _rebalance(self):
17 if len(self._low) > len(self._high) + 1:
18 heapq.heappush(self._high, -heapq.heappop(self._low))
19 elif len(self._high) > len(self._low):
20 heapq.heappush(self._low, -heapq.heappop(self._high))
21 
22 @property
23 def median(self):
24 if not self._low:
25 raise ValueError("no data points yet")
26 if len(self._low) > len(self._high):
27 return float(-self._low[0])
28 return (-self._low[0] + self._high[0]) / 2.0
29 
30 
31def stream_medians(values):
32 tracker = MovingMedian()
33 for value in values:
34 tracker.add(value)
35 yield tracker.median
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Two heaps split around the middle let you read the median from the roots in constant time.
  2. 2Python only ships a min-heap, so negating values turns `_low` into a max-heap.
  3. 3Enforcing a size invariant after every insert is what keeps the median at the heap roots.

Related explainers

rust 
use axum::{
    body::Body,
    extract::State,
    http::{header, StatusCode},

Streaming a DB migration with Axum

streaming keyset-pagination backpressure
Advanced 8 steps
typescript 
interface RunningStats {
  count: number;
  total: number;
  average: number;

Streaming running averages in TypeScript

generators streaming incremental-aggregation
Intermediate 6 steps
python 
import json
import logging
import threading
from pathlib import Path

A hot-reloading config file watcher

file-watching thread-safety hot-reload
Intermediate 7 steps
python 
class Parser:
    def __init__(self, text):
        self.tokens = self._tokenize(text)
        self.pos = 0

A recursive descent arithmetic parser

recursive-descent tokenizer operator-precedence
Intermediate 9 steps
python 
import re
from dataclasses import dataclass, field
 
 

Building a table of contents from Markdown

regular-expressions parsing slugification
Intermediate 9 steps
python 
from flask import Blueprint, render_template, redirect, url_for, session, request
from wtforms import Form, StringField, SelectField, IntegerField
from wtforms.validators import DataRequired, Email, NumberRange
 

A multi-step signup wizard in Flask

blueprints session-state form-validation
Intermediate 10 steps

Share this explainer

Here's the card — post it anywhere.

Running median with two heaps — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code