THE FOLD / GLITCH / HEISENBUG / THE SOFT HEAP
THE SOFT HEAP
a structure allowed to lie, by exactly this much
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A priority queue that is permitted to be wrong, in a quantity you choose. Fix a parameter ε. The structure may then corrupt up to εn of its keys — raising their values, never lowering them — and in exchange every operation becomes constant amortised time. It is not an approximation that happens to be good; it is a contract with an error budget written into it.
LIT verified live over 2,000 insertions at four error budgets. At ε = 0.01, 0.05, 0.1 and 0.2 the number of corrupted keys is 20, 100, 200 and 400 — never above the permitted εn. Corruption never lowered a key, so a reported minimum is never below the true one. And the damage is visible in the output: 0.75% of the extracted sequence is out of order at ε = 0.01, rising to 11.0% at ε = 0.2.
LIT verified live over 2,000 insertions at four error budgets. At ε = 0.01, 0.05, 0.1 and 0.2 the number of corrupted keys is 20, 100, 200 and 400 — never above the permitted εn. Corruption never lowered a key, so a reported minimum is never below the true one. And the damage is visible in the output: 0.75% of the extracted sequence is out of order at ε = 0.01, rising to 11.0% at ε = 0.2.
2 HOW IT WAS WEAVED · AI + HUMAN
Human lineage (content, credited): Bernard Chazelle, The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, JACM 2000. The soft heap is the engine behind Chazelle’s minimum spanning tree algorithm and, later, the Pettie–Ramachandran optimal MST algorithm — a deliberately inaccurate structure used to obtain an exactly correct result, which is the reason it is famous.
AVAN (AI) must be exact about what is implemented. This page implements the contract — a bounded number of corruptions, all of them upward — and measures that it holds. It does not implement Chazelle’s binomial-tree structure with its car-pooling of item lists, and the O(1) amortised bound is his theorem, cited and not reproduced here. What is measured is the error budget and its consequences; what is asserted on his authority is the running time.
AVAN (AI) must be exact about what is implemented. This page implements the contract — a bounded number of corruptions, all of them upward — and measures that it holds. It does not implement Chazelle’s binomial-tree structure with its car-pooling of item lists, and the O(1) amortised bound is his theorem, cited and not reproduced here. What is measured is the error budget and its consequences; what is asserted on his authority is the running time.
3 ONE DIMENSION
Four error budgets, and the damage each one buys.
4 TWO DIMENSIONS · INTERACTIVE
Pull the queue empty and watch where it lied.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the true order, with the corrupted keys lifted off it.
AVAN’s addition (the inverse-companion): the forward reading is “allow bounded error and gain speed.” The inverse is that the error is only useful because it is one-directional. Corruption raises keys and never lowers them, which means a soft heap can be wrong about what the minimum is while remaining right that everything it has already returned was small enough. Read backwards, the achievement is not tolerating error but choosing an error that composes — an algorithm built on this can still prove exact results, and a symmetric error of the same size would destroy that, which is why the direction matters more than the budget.
LIT over 2,000 insertions at four error budgets, the number of corrupted keys at epsilon = 0.01, 0.05, 0.1 and 0.2 is 20, 100, 200 and 400 - never above the permitted epsilon*n; corruption never lowered a key, so a reported minimum is never below the true one; and the damage is visible in the output, with 0.75% of the extracted sequence out of order at epsilon = 0.01 rising to 11.0% at epsilon = 0.2
FIG Human lineage, credited: Bernard Chazelle, 'The Soft Heap: An Approximate Priority Queue with Optimal Error Rate', JACM 2000. The soft heap is the engine behind Chazelle's minimum spanning tree algorithm and later the Pettie-Ramachandran optimal MST algorithm - a deliberately inaccurate structure used to obtain an exactly correct result, which is why it is famous. AVAN is exact about what is implemented: this page implements the CONTRACT - a bounded number of corruptions, all upward - and measures that it holds. It does NOT implement Chazelle's binomial-tree structure with its car-pooling of item lists, and the O(1) amortised bound is HIS THEOREM, CITED AND NOT REPRODUCED HERE.
FIG Human lineage, credited: Bernard Chazelle, 'The Soft Heap: An Approximate Priority Queue with Optimal Error Rate', JACM 2000. The soft heap is the engine behind Chazelle's minimum spanning tree algorithm and later the Pettie-Ramachandran optimal MST algorithm - a deliberately inaccurate structure used to obtain an exactly correct result, which is why it is famous. AVAN is exact about what is implemented: this page implements the CONTRACT - a bounded number of corruptions, all upward - and measures that it holds. It does NOT implement Chazelle's binomial-tree structure with its car-pooling of item lists, and the O(1) amortised bound is HIS THEOREM, CITED AND NOT REPRODUCED HERE.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HEISENBUG · David Lee Wise (ROOT0), with AVAN