Pattern Reference
Two Heaps
"Median from data stream, sliding window median, IPO capital, schedule tasks."
Loading...
Deep Dive Tutorial
Two heaps maintain the median of a dynamic dataset by splitting elements into two halves: a max-heap holding the lower half, and a min-heap holding the upper half. The invariant: max-heap size equals min-heap size (even count) or is exactly 1 larger (odd count). Median = top of max-heap (odd) or average of both tops (even). Every insert: add to correct heap, rebalance if sizes differ by 2.
Two heaps template for median maintenance
// JavaScript lacks a built-in heap — use a sorted structure or implement one
class MinHeap {
constructor() { this.h = []; }
push(x) {
this.h.push(x);
let i = this.h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p] <= this.h[i]) break;
[this.h[p], this.h[i]] = [this.h[i], this.h[p]];
i = p;
}
}
pop() {
const top = this.h[0];
const last = this.h.pop();
if (this.h.length) {
this.h[0] = last;
let i = 0;
while (true) {
let s = i, l = 2*i+1, r = 2*i+2;
if (l < this.h.length && this.h[l] < this.h[s]) s = l;
if (r < this.h.length && this.h[r] < this.h[s]) s = r;
if (s === i) break;
[this.h[s], this.h[i]] = [this.h[i], this.h[s]];
i = s;
}
}
return top;
}
peek() { return this.h[0]; }
size() { return this.h.length; }
}
class MaxHeap extends MinHeap {
push(x) { super.push(-x); }
pop() { return -super.pop(); }
peek() { return -super.peek(); }
}
// Two-heap median tracker
class MedianFinder {
constructor() { this.lo = new MaxHeap(); this.hi = new MinHeap(); }
addNum(n) {
this.lo.push(n);
this.hi.push(this.lo.pop()); // ensure lo.peek() <= hi.peek()
if (this.lo.size() < this.hi.size()) this.lo.push(this.hi.pop());
}
findMedian() {
if (this.lo.size() > this.hi.size()) return this.lo.peek();
return (this.lo.peek() + this.hi.peek()) / 2;
}
}Worked Problems
scale
Two heap invariant: max-heap (lo) holds lower half, min-heap (hi) holds upper half. Always: lo.peek() ≤ hi.peek(). Sizes: lo.size ∈ {hi.size, hi.size + 1}.
Insert protocol:
1. Push to lo
2. Move lo's max to hi (ensures lo.peek() ≤ hi.peek())
3. If lo.size < hi.size: move hi's min to lo (restore size invariant)
Median: odd total → lo.peek(). Even total → (lo.peek() + hi.peek()) / 2
Applications: anywhere you need online median, "k-th from each half," or "split dataset at dynamic threshold."
Insert protocol:
1. Push to lo
2. Move lo's max to hi (ensures lo.peek() ≤ hi.peek())
3. If lo.size < hi.size: move hi's min to lo (restore size invariant)
Median: odd total → lo.peek(). Even total → (lo.peek() + hi.peek()) / 2
Applications: anywhere you need online median, "k-th from each half," or "split dataset at dynamic threshold."