Heap, selection, and stream · HTML
lower is a max-heap and upper a min-heap. Require max(lower) <= min(upper), with equal sizes or exactly one extra item in lower.
Recognition signals
- Values arrive one by one and the median is queried after insertions.
- The answer depends on the middle boundary but not on a full ordering.
- The set must be dynamically balanced into lower and upper halves.
- Deletion is absent or can be handled by an added lazy-deletion layer.
- The desired bounds are O(log n) insertion and O(1) query.
False friends
| Signal | Why it is different |
|---|
| One query on a static array | Quickselect is expected linear; two heaps pay log n to preserve an online answer. |
| Sliding-window median | The skeleton still works, but it needs delayed deletion, logical heap sizes, and root pruning. |
| A tiny bounded value domain | Frequency buckets and rank scans may be simpler and support deletion naturally. |
Core invariant
Every lower-half item is no greater than every upper-half item; lower has the same size as upper or exactly one extra item.
State, transition, and processing order
| Item | Definition |
|---|
| State | A negated-value heap for lower and a min-heap for upper; deletion variants add delayed counts and logical sizes. |
| Transition | Place the new value according to the lower root, then move the root of an oversized side across the boundary. |
| Frontier / order | The lower root is the greatest lower-half value and the upper root is the least upper-half value; together they are the median boundary. |
Python skeleton
from heapq import heappop, heappush
class MedianStream:
def __init__(self):
self.lower, self.upper = [], []
def add(self, x):
if not self.lower or x <= -self.lower[0]:
heappush(self.lower, -x)
else:
heappush(self.upper, x)
if len(self.lower) > len(self.upper) + 1:
heappush(self.upper, -heappop(self.lower))
elif len(self.upper) > len(self.lower):
heappush(self.lower, -heappop(self.upper))
def median(self):
if not self.lower:
raise ValueError('empty stream')
if len(self.lower) > len(self.upper):
return -self.lower[0]
return (-self.lower[0] + self.upper[0]) / 2
Correctness sketch
- Boundary-based insertion preserves cross-heap ordering.
- If one side grows too large, its root is the closest item to the split and the only item that should cross; moving it restores size without breaking order.
- The size convention places the middle one or two ranks at the roots, so the query formula is correct.
Complexity
| Time | Space | Parameters |
|---|
| O(log n) per add and O(1) per median | O(n) | n is the number of currently valid values. |
Edge cases
- querying an empty stream
- duplicate values
- negatives plus lower-heap negation
- return type for even length
- physical versus logical size under deletion
Error patterns
| Pattern | Why it fails / fix |
|---|
| Balancing sizes only | Two arbitrary equal halves do not expose a median; cross-heap order is a separate invariant. |
| Losing a lower-heap sign | Comparisons, transfers, and returns must distinguish stored negatives from logical values. |
| Removing a window value with list.remove | That destroys heap bounds. Use delayed counts and logical sizes. |
| No convention for the extra item | Insertion, balancing, and odd-length queries become inconsistent unless one side is designated. |
Selection and exclusion rules
- Use two heaps for continuous insertion and median queries.
- Use Quickselect for one static median.
- For a sliding window, add lazy deletion or use an ordered multiset.
- Consider frequency buckets for a small bounded domain.
Original micro-example
| Part | Detail |
|---|
| Result | The middle boundaries are 4 and 6, so the median is 5. |
| Setup | Temperatures arrive as 4,10,6,2. |
| Trace | 4 enters lower, 10 upper; 6 enters upper then moves to lower; 2 enters lower and pushes 6 back to upper. |
Recall prompts
My notes