Median of a Stream II

Find the median — or any quantile — of a dataset too large to keep in memory. Implement HistogramQuantile(lo, hi, buckets), which uses fixed memory regardless of stream length.

Bucket width is w = (hi - lo) / buckets; add(x) counts x in the underflow bucket when x < lo, the overflow bucket when x >= hi, otherwise bucket floor((x - lo) / w). quantile(q) (for 0 < q <= 1) walks underflow, buckets 0 … buckets - 1, overflow, accumulating counts, and answers from the first bucket whose cumulative count reaches q × n: lo for underflow, hi for overflow, otherwise the bucket's midpoint lo + (j + 0.5) × w. null when empty.

h = HistogramQuantile(0, 100, 10)         // width 10
for x in 5, 15, 25, ..., 95: h.add(x)     // one value per bucket
h.quantile(0.5)   ->  45                  // midpoint of the fifth bucket
h.quantile(0.99)  ->  95
h.add(150)                                // overflow
h.quantile(1.0)   ->  100