THE FOLD / SPAWN / SECOND WIND / THE BRODAL QUEUE
THE BRODAL QUEUE
worst case, not amortised -- and what that costs
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Brodal’s 1996 priority queue does insert, meld and find-min in worst-case constant time — not amortised. The distinction is the whole point: an amortised bound promises a good average and permits an occasional spike, and there are systems where the spike is the only number that matters.
LIT verified live against a binomial heap, where meld walks both root lists. Melding two heaps of 65,535 costs 32 steps against Brodal’s 1. And on inserts: across 4,096 operations the amortised cost is 2.000 steps while a single insert costs 13 — 6.5× the average — landing exactly at insert 4,095, which is 212−1, where the binary counter carries all the way.
LIT verified live against a binomial heap, where meld walks both root lists. Melding two heaps of 65,535 costs 32 steps against Brodal’s 1. And on inserts: across 4,096 operations the amortised cost is 2.000 steps while a single insert costs 13 — 6.5× the average — landing exactly at insert 4,095, which is 212−1, where the binary counter carries all the way.
2 HOW IT WAS WEAVED · AI + HUMAN
Gerth Stølting Brodal published the structure in 1996, answering a question that had been open since Fredman and Tarjan’s Fibonacci heap gave the same bounds amortised. It is famous for being theoretically decisive and almost never implemented.
AVAN (AI) measures the gap Brodal closes rather than the structure itself, because that gap is the reason anyone cares. The binomial heap is right there to be measured: its insert is amortised O(1) and worst-case O(log n), and the spike is not random — it lands precisely where a binary counter rolls over. Naming where the worst case occurs is more useful than naming how big it is, and it is the part an average conceals by construction.
AVAN (AI) measures the gap Brodal closes rather than the structure itself, because that gap is the reason anyone cares. The binomial heap is right there to be measured: its insert is amortised O(1) and worst-case O(log n), and the spike is not random — it lands precisely where a binary counter rolls over. Naming where the worst case occurs is more useful than naming how big it is, and it is the part an average conceals by construction.
3 ONE DIMENSION
Four thousand inserts, and where the cost spikes.
4 TWO DIMENSIONS · INTERACTIVE
Meld two heaps and compare the two promises.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a flat line and a line with towers.
AVAN’s addition (the inverse-companion): the forward reading is “worst-case beats amortised.” The inverse is that the worst-case guarantee is bought with a constant factor that makes it slower almost always. Brodal’s structure is universally acknowledged as impractical; the binomial heap with its occasional 13-step insert wins on real workloads by a wide margin. Read backwards, the choice is not between a good bound and a bad one — it is between being fast on average and being predictable, and only a system with a deadline is right to pay for the second.
LIT melding two binomial heaps of 65,535 costs 32 steps against Brodal's 1, and across 4,096 inserts the amortised cost is 2.000 steps while a single insert costs 13 - 6.5 times the average - landing exactly at insert 4,095, which is 2^12 - 1, where the binary counter carries all the way
FIG Gerth Stolting Brodal published the structure in 1996, answering a question open since Fredman and Tarjan's Fibonacci heap gave the same bounds amortised. It is famous for being theoretically decisive and almost never implemented. AVAN measures the GAP BRODAL CLOSES rather than the structure itself, because that gap is the reason anyone cares: the binomial heap is right there to be measured, its insert amortised O(1) and worst-case O(log n), and the spike is not random - it lands precisely where a binary counter rolls over. Naming WHERE the worst case occurs is more useful than naming how big it is, and it is the part an average conceals by construction.
FIG Gerth Stolting Brodal published the structure in 1996, answering a question open since Fredman and Tarjan's Fibonacci heap gave the same bounds amortised. It is famous for being theoretically decisive and almost never implemented. AVAN measures the GAP BRODAL CLOSES rather than the structure itself, because that gap is the reason anyone cares: the binomial heap is right there to be measured, its insert amortised O(1) and worst-case O(log n), and the spike is not random - it lands precisely where a binary counter rolls over. Naming WHERE the worst case occurs is more useful than naming how big it is, and it is the part an average conceals by construction.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN