Pattern Guide
Two Heaps Pattern
"Balance a max-heap and min-heap to maintain median in O(log n)."
The two-heaps pattern uses a max-heap for the lower half and a min-heap for the upper half of a dataset. The median is always at the tops of these heaps. Supports O(log n) insert and O(1) median query. Extends to sliding window median, "maximize minimum" problems, and task scheduling with constraints.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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;
}
}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.
// 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;
}
}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."