A Binary Heap answers exactly one question fast:
what's smallest right now (or, flipped, what's largest — never both from the same heap). Needing
both from one live, changing structure is a genuinely different problem, and the obvious fix
doesn't work: keeping a separate min-heap and max-heap copy of the same data means every insert
and delete has to happen twice, and the two copies have no way to tell each other where an element
that was just removed from one used to sit in the other. A Min-Max Heap answers
both from a single array, in a single tree shape, with the same O(log n)
insert/delete cost a plain heap already has and O(1) for both extremes at once. The
entire trick is one extra rule layered on top of the ordinary complete-binary-tree array shape
every heap on this site already uses: levels alternate between guaranteeing a minimum and
guaranteeing a maximum, and the guarantee holds against every descendant below a node, not
just its immediate children.
The root (level 0) is a min level — shown in black — guaranteed smaller than
every single node beneath it anywhere in the tree, not just its two children. Level 1 is a
max level — shown in red — each of its (at most two) nodes guaranteed bigger than
everything in its own subtree. Level 2 is min again, level 3 max, and so on, all the way down.
Insert a value and watch it trickle up through parent and grandparent comparisons; delete the
minimum or maximum and watch the last element drop in and trickle back down. The stats line always
reports both extremes directly, since finding either one is O(1) here.
The maximum is always one of exactly two candidates. Because every max-level
node is bigger than its entire subtree, and level 1 holds the only max-level nodes directly under
the root, the single largest value in the whole heap has to be one of the root's two children —
nowhere else could it hide without violating some max level's guarantee on the way there. So
findMax is a straight O(1) comparison of at most two values (one, if the
heap has exactly two elements; the root itself, if it has exactly one). findMin is
even simpler: the root is the minimum, full stop, the same as a plain heap.
Trickling up compares with the grandparent, not the parent — on purpose. A newly inserted value at a min-level index first checks its immediate parent, which sits on a max level: if the new value is bigger than that parent, it violates the parent's max guarantee, so they swap and the new value continues trickling up the max chain from there instead. If it isn't bigger, the parent poses no problem at all — but the new value could still be smaller than some earlier ancestor on its own level type, two levels up, which is the grandparent. So the min-side trickle-up skips the parent entirely and keeps comparing against the grandparent, great-great-grandparent, and so on, swapping and climbing two levels at a time while the new value is smaller. Comparing against the immediate parent instead of the grandparent during this second phase is exactly the mistake measured in Pitfalls below — it looks reasonable and breaks the invariant almost every time.
Trickling down has to look at grandchildren too, and re-check one more comparison after
swapping with one. When deleteMin drops the last element into the root and
sifts it down, the candidate to swap with isn't just the smaller of the two children — a min-level
guarantee has to hold against every descendant, so the candidate is the smallest among up
to two children and up to four grandchildren. If that overall smallest value lives at a
grandchild and is smaller than the sinking element, they swap — but that same swap can just as
easily break the guarantee at the grandchild's own immediate parent (a max-level node, one level
below the node being sifted), since whatever value the swap just pushed down there might now be
bigger than it. The algorithm re-checks that one specific comparison immediately after the swap and
fixes it on the spot, before continuing to sift further down from the grandchild's original
position. Skip that recheck and the sift moves past that spot for good, leaving a real violation
sitting one level below where the swap happened — measured directly in Pitfalls.
function level(i) {
let lvl = 0, start = 0, size = 1;
while (i >= start + size) { start += size; size *= 2; lvl++; }
return lvl;
}
const parent = (i) => Math.floor((i - 1) / 2);
const grandparent = (i) => (i < 3 ? -1 : parent(parent(i)));
const isMinLevel = (i) => level(i) % 2 === 0;
class MinMaxHeap {
#a = [];
size() { return this.#a.length; }
#swap(i, j) { [this.#a[i], this.#a[j]] = [this.#a[j], this.#a[i]]; }
findMin() { return this.#a.length ? this.#a[0] : null; }
findMax() {
const n = this.#a.length;
if (n === 0) return null;
if (n === 1) return this.#a[0];
if (n === 2) return this.#a[1];
return this.#a[1] >= this.#a[2] ? this.#a[1] : this.#a[2]; // one of exactly two candidates
}
#children(i) {
const n = this.#a.length, out = [];
if (2 * i + 1 < n) out.push(2 * i + 1);
if (2 * i + 2 < n) out.push(2 * i + 2);
return out;
}
#grandchildren(i) {
const out = [];
for (const c of this.#children(i)) out.push(...this.#children(c));
return out;
}
#pushUpMin(i) {
let gp = grandparent(i);
while (gp !== -1 && this.#a[i] < this.#a[gp]) { this.#swap(i, gp); i = gp; gp = grandparent(i); }
}
#pushUpMax(i) {
let gp = grandparent(i);
while (gp !== -1 && this.#a[i] > this.#a[gp]) { this.#swap(i, gp); i = gp; gp = grandparent(i); }
}
insert(x) {
this.#a.push(x);
const i = this.#a.length - 1;
if (i === 0) return;
const p = parent(i);
if (isMinLevel(i)) {
if (this.#a[i] > this.#a[p]) { this.#swap(i, p); this.#pushUpMax(p); }
else this.#pushUpMin(i);
} else {
if (this.#a[i] < this.#a[p]) { this.#swap(i, p); this.#pushUpMin(p); }
else this.#pushUpMax(i);
}
}
#pushDownMin(i) {
for (;;) {
const kids = this.#children(i), gkids = this.#grandchildren(i);
const cands = kids.concat(gkids);
if (cands.length === 0) break;
let m = cands[0];
for (const c of cands) if (this.#a[c] < this.#a[m]) m = c;
if (gkids.includes(m)) {
if (this.#a[m] >= this.#a[i]) break;
this.#swap(m, i);
const p = parent(m); // m's own immediate parent
if (this.#a[m] > this.#a[p]) this.#swap(m, p); // re-check, fix on the spot
i = m;
} else {
if (this.#a[m] < this.#a[i]) this.#swap(m, i);
break;
}
}
}
#pushDownMax(i) { // exact mirror of #pushDownMin with every comparison flipped
for (;;) {
const kids = this.#children(i), gkids = this.#grandchildren(i);
const cands = kids.concat(gkids);
if (cands.length === 0) break;
let m = cands[0];
for (const c of cands) if (this.#a[c] > this.#a[m]) m = c;
if (gkids.includes(m)) {
if (this.#a[m] <= this.#a[i]) break;
this.#swap(m, i);
const p = parent(m);
if (this.#a[m] < this.#a[p]) this.#swap(m, p);
i = m;
} else {
if (this.#a[m] > this.#a[i]) this.#swap(m, i);
break;
}
}
}
deleteMin() {
if (this.#a.length === 0) return null;
const min = this.#a[0];
const last = this.#a.pop();
if (this.#a.length > 0) { this.#a[0] = last; this.#pushDownMin(0); }
return min;
}
deleteMax() {
const n = this.#a.length;
if (n === 0) return null;
const idx = n === 1 ? 0 : (n === 2 ? 1 : (this.#a[1] >= this.#a[2] ? 1 : 2));
const max = this.#a[idx];
const last = this.#a.pop();
if (idx < this.#a.length) { this.#a[idx] = last; this.#pushDownMax(idx); }
return max;
}
}Verified against a naive multiset reference (a plain array, re-sorted on every query) across
20,000 randomized trials of up to 40 interleaved insert/delete-min/delete-max operations each —
every extracted value matched the reference's true min or max, sizes stayed in sync, and a full
level-by-level invariant check (every node against every child and every grandchild, not
just children) passed after every single operation, 0 mismatches. A separate pass
drained 3,000 randomly built heaps completely two ways — repeated deleteMin and,
independently, repeated deleteMax on a fresh copy of the same elements — and checked
the output against Array.sort() both ascending and descending: 0
mismatches, confirming this doubles as a min-max-heapsort. Edge cases checked directly:
empty heap (findMin/findMax both null), a single element
(both extremes equal that element), and an all-duplicate heap of three equal values (still a valid
heap, both deletions return the duplicate correctly). This page's own demo script below reimplements
the same logic with path-tracking added for the highlight animation, exercised the same way against
the reference before shipping.
Comparing against the parent instead of the grandparent when trickling up silently
breaks the invariant almost every time. It's a natural mistake: a plain Binary Heap's
sift-up only ever looks at the immediate parent, so carrying that same instinct into the min-side
or max-side chain here (once the immediate-parent check has already been handled) looks like the
obvious continuation. It isn't — the parent is the wrong level type to compare a same-level
guarantee against. Measured directly: swapping grandparent(i) for
parent(i) in the trickle-up chain and running 3,000 randomized insert-only sequences
produced an invalid heap 99.6% of the time.
Skipping the grandchild's-own-parent recheck after a trickle-down swap leaves a real,
silent violation one level below where the swap happened. The swap moves a smaller value
up into an internal node, but whatever value it displaced downward into the grandchild's old slot
might now be bigger than the grandchild's immediate parent — a comparison the algorithm has to make
and fix on the spot, not defer, because the sift never comes back that way again. Measured directly:
removing that one recheck and running a single deleteMin after 5,000 randomly built
heaps (5-34 elements each) left the heap invalid 10.8% of the time — a fraction low
enough that a handful of manual spot-checks on small examples would plausibly miss it entirely.
findMax needs its own size-1 and size-2 cases, not just
max(a[1], a[2]). The "maximum is one of two candidates" shortcut only holds
once both of the root's children actually exist. A heap of exactly one element has neither, so the
maximum is the root itself; a heap of exactly two has only a[1], and reading
a[2] anyway hits undefined — Math.max(a[1], undefined)
evaluates to NaN in JavaScript, not a clean crash and not an obviously wrong-looking
number either. Measured directly: naive max(a[1], a[2]) against 2,000 randomly built
one- or two-element heaps was wrong 100% of the time at those two sizes
specifically (correct at every larger size tested alongside it).
Time: insert, deleteMin, and deleteMax
are all O(log n) — the trickle chains climb or descend two levels per comparison
instead of one, so the real constant factor is roughly half a plain
Binary Heap's, but the asymptotic bound is identical, for
the same reason: a complete binary tree has height O(log n) regardless of which
levels alternate what. findMin and findMax are both O(1) —
see Why It Works for why the maximum in particular never needs more than a two-value comparison.
Space: O(n), one flat array, zero pointers — identical to a plain
heap; the alternating-level rule is purely a rule about which comparisons get made, not an extra
field stored anywhere.
This site's guide, Choosing a Range Query Structure, sets this entry aside the same way it already sets aside Binary Heap itself — repeatedly reporting an extreme value out of a changing set isn't a query over an arbitrary range of array positions, the question every other entry there answers. If a single extreme is all that's ever needed, the plain Binary Heap is simpler code and a smaller constant factor for exactly that reason; reach for this entry specifically when both ends of the same live, changing set need to come out cheaply, without paying for two unsynchronized heaps.