Data Structures19 sections · 729 units
Open in Course

Median Stream - Invariants

What to maintain

Two invariants to maintain:

1.1. Size balance: the heaps' sizes differ by at most 11. If they differ, the larger heap has the median.

2.2. Value ordering: all elements in max-heap (smaller half) are ≤\leq all elements in min-heap (larger half). Insertion strategy:

  • Add to max-heap first (smaller half)
  • Move max-heap's root to min-heap (ensure ordering)
  • If min-heap is larger, move its root back to max-heap (ensure balance)