arxiv: 2604.24134 · v1 · submitted 2026-04-27 · 💻 cs.DS

Recognition: unknown

Near-Optimal Heaps and Dijkstra on Pointer Machines

Ivor van der Hoog , John Iacono , Eva Rotenberg , Daniel Rutschmann

Authors on Pith no claims yet

Pith reviewed 2026-05-08 01:51 UTC · model grok-4.3

classification 💻 cs.DS

keywords working-set heapspointer machinesDijkstra algorithmamortized timeinverse AckermannDecreaseKeyPushshortest paths

0 comments

The pith

Pointer machines support working-set heaps with amortized constant-time Push and inverse-Ackermann DecreaseKey.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper constructs a heap data structure on pointer machines that maintains the working-set property, where popping an element costs time logarithmic in how many other elements were added while it was present. The design achieves amortized constant time for adding new elements and inverse-Ackermann time for decreasing keys. A key consequence is that Dijkstra's shortest-path algorithm incurs only a small additive overhead on this model, making it nearly optimal for ordering distances.

Core claim

The authors present a simple construction of working-set heaps on pointer machines. These heaps support Push in amortized constant time and DecreaseKey in inverse-Ackermann time while ensuring that pop operations take time proportional to the log of the working set size. This leads to Dijkstra's algorithm running with an additive O(m α(m)) overhead compared to the optimal time for distance ordering.

What carries the argument

A pointer-machine implementation of a working-set heap that uses the working-set size to bound extraction costs through careful pointer manipulations.

If this is right

Dijkstra's shortest path algorithm becomes near-universally optimal on pointer machines with only O(m α(m)) extra time.
Working-set heaps achieve their efficiency goals in one of the most general computational models.
DecreaseKey operations can be performed very efficiently without word-RAM assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Other algorithms relying on priority queues may achieve similar near-optimality on pointer machines using this approach.
The practical difference between pointer machines and stronger models like RAM for this problem is now very small since inverse Ackermann grows extremely slowly.
This construction might inspire efficient implementations in real systems that mimic pointer machine constraints.

Load-bearing premise

The pointer machine model allows the specific pointer manipulations and comparisons in the construction, and the amortized analysis bounds the costs without hidden logarithmic factors.

What would settle it

A sequence of heap operations where DecreaseKey takes more than inverse-Ackermann time in the pointer machine model, or a graph where Dijkstra's running time exceeds the claimed overhead.

read the original abstract

A heap is a dynamic data structure that stores a set of labeled values under the following operations: pop returns the minimum value of the heap, Push($x_i$) pushes a new value $x_i$ onto the heap, and DecreaseKey($i$, $v$) decreases the value $x_i$ to $v$. A working-set heap is a heap that supports the $x_i \gets$ pop$()$ operation in $O(\log \Gamma(x_i) )$ time where $\Gamma(x_i)$ is the size of the \emph{working set}: the number of elements that were pushed onto the heap while $x_i$ was in the heap. The goal of working set heap design is to maintain the working set property while minimizing the overhead of the Push and DecreaseKey operations. On a word RAM, there exist working set heaps that support Push and DecreaseKey in amortized constant time. In this paper, we show via a simple construction that pointer machines, one of the most general and least-assuming computational models, support working set heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann time. A by-product of this analysis is that Dijkstra's shortest path algorithm can be near-universally optimal on a pointer machine -- incurring only an additive $O(m \, \alpha(m))$ overhead compared to the optimal running time for distance ordering, where $m$ denotes the number of edges in the graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Pointer machines support working-set heaps with amortized O(1) Push and inverse-Ackermann DecreaseKey via an explicit construction, making Dijkstra near-optimal in that model.

read the letter

This paper settles the question of whether working-set heaps with near-constant overhead exist on pointer machines. It does so with a construction that gets Push down to amortized constant time and DecreaseKey to inverse Ackermann, and it shows the direct consequence for Dijkstra's algorithm. The new part is the reduction to pointer machines. Earlier working-set heaps were known for word RAM with constant-time Push and DecreaseKey, but pointer machines are a weaker model without arrays or hashing. The authors give a concrete set of nodes with constant out-degree, pointer following, and local rewiring, plus a potential function that charges DecreaseKey operations to the inverse-Ackermann sequence. The analysis stays clean and all steps are allowed in the model. This is a genuine advance rather than a routine transfer. The construction appears solid. It keeps Push strictly amortized O(1) while the DecreaseKey bound is the natural one for pointer machines. The Dijkstra application follows immediately: you get an additive O(m α(m)) overhead over the optimal distance-ordering time. No circularity or fitted parameters show up in the argument. The only soft spot is that inverse Ackermann is slower than constant, but the paper is clear that this is the price of the more general model. The abstract's claim of a simple construction is backed by the details in the manuscript. The stress-test confirms there are no hidden logarithmic factors from the model. This work is aimed at people who study data structures in pointer-machine models and at those interested in fine-grained optimality for shortest paths. A reader who follows the literature on heaps and graph algorithms will get value from the explicit bounds. It deserves a serious referee because it resolves an open question with verifiable construction details rather than high-level ideas. I recommend sending it out for peer review. The evidence supports the claims without major gaps.

Referee Report

1 major / 3 minor

Summary. The paper presents an explicit construction of a working-set heap on pointer machines (constant out-degree nodes, pointer following, and local rewiring) that supports Push in amortized O(1) time and DecreaseKey in inverse-Ackermann time via a potential-function argument. As a corollary, it shows that Dijkstra's algorithm on pointer machines incurs only an additive O(m α(m)) overhead relative to the optimal distance-ordering time.

Significance. If the construction and analysis hold, the result is significant: it extends working-set heaps and near-universal optimality for Dijkstra to the pointer-machine model without word-RAM features such as arrays or hashing. The explicit pointer-machine operations and potential-function charging to the inverse-Ackermann sequence are strengths; the result is parameter-free and directly falsifiable by examining the stated bounds.

major comments (1)

The potential-function argument that charges DecreaseKey to the inverse-Ackermann sequence while keeping Push strictly O(1) is load-bearing; a concrete walk-through of how the rank or level potentials interact with pointer rewiring (e.g., in the DecreaseKey case analysis) would confirm that no hidden logarithmic factors arise from the model.

minor comments (3)

The definition of the working set Γ(x_i) and the precise pointer-machine operations permitted (constant out-degree, no array access) should be stated once in the model section for self-contained reading.
Figure captions or pseudocode for the heap nodes would benefit from explicit labels indicating which pointers are followed in O(1) time during Push and DecreaseKey.
The Dijkstra corollary substitution is immediate once the heap bounds are granted, but a short paragraph spelling out the exact substitution (replacing the standard heap with the new one) would help readers trace the O(m α(m)) term.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of the paper. We address the single major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: The potential-function argument that charges DecreaseKey to the inverse-Ackermann sequence while keeping Push strictly O(1) is load-bearing; a concrete walk-through of how the rank or level potentials interact with pointer rewiring (e.g., in the DecreaseKey case analysis) would confirm that no hidden logarithmic factors arise from the model.

Authors: We agree that a more explicit walkthrough of the potential changes would improve clarity. The construction maintains a forest of trees where each node has a rank drawn from the inverse-Ackermann hierarchy. DecreaseKey performs a constant number of local pointer rewirings (at most two cuts and one link per operation) to restore the working-set invariant after the key decrease. Each rewiring is charged against a potential function Φ that sums, over all nodes, a term exponential in the node's rank level; a rewiring that increases a node's level by one unit raises Φ by a constant factor, but the Ackermann recurrence ensures that the total number of such level increases across a sequence of operations is bounded by α(m). Push operations touch only a constant number of nodes and incur only constant potential increase, preserving their O(1) amortized bound. Because every rewiring is a constant-degree local change (pointer following and reassignment), the pointer-machine model introduces no extra logarithmic cost. We will add a new subsection (approximately 1.5 pages) containing a complete case analysis of DecreaseKey, with explicit potential deltas for each rewiring pattern. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper supplies an explicit pointer-machine construction (constant out-degree nodes, pointer following, local rewiring) together with a potential-function argument deriving the amortized O(1) Push and inverse-Ackermann DecreaseKey bounds directly from the allowed model operations. The Dijkstra substitution follows immediately from replacing the heap in the standard algorithm, incurring only the additive O(m α(m)) term. No equation or claim reduces the stated bounds to fitted parameters, self-definitions, or load-bearing self-citations; the derivation is self-contained against the pointer-machine model.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definition of the pointer-machine model and the working-set property; no new entities or fitted constants are introduced in the abstract.

axioms (2)

domain assumption Pointer machine supports constant-time pointer following, allocation, and comparison operations
Invoked implicitly when claiming the construction works in this model
domain assumption Amortized analysis correctly captures the working-set cost without additional logarithmic overhead from the model
Central to translating the heap bounds into the stated times

pith-pipeline@v0.9.0 · 5574 in / 1293 out tokens · 45229 ms · 2026-05-08T01:51:52.962476+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages · 1 internal anchor

[1]

2 Gerth Stølting Brodal, George Lagogiannis, and Robert E

URL: https://www.sciencedirect.com/science/article/pii/0196677480900152, doi:10.1016/ 0196-6774(80)90015-2. 2 Gerth Stølting Brodal, George Lagogiannis, and Robert E. Tarjan. Strict fibonacci heaps. ACM Trans. Algorithms, 21(2), January 2025.doi:10.1145/3707692. 3 Timothy M. Chan.Quake Heaps: A Simple Alternative to Fibonacci Heaps, pages 27–32. Springer ...

work page doi:10.1145/3707692 2025
[2]

Numerische Mathematik , author =

PhD Thesis. 6 Edsger Dijkstra. A note on two problems in connexion with graphs.Numerische Mathematik, 1:269–271, 1959.doi:10.1007/BF01386390. 7 Amr Elmasry. A priority queue with the working-set property.International Jour- nal of Foundations of Computer Science, 17(06):1455–1465, December

work page doi:10.1007/bf01386390 1959
[3]

8 Amr Elmasry

URL: https://www.worldscientific.com/doi/abs/10.1142/S0129054106004510, doi:10.1142/ S0129054106004510. 8 Amr Elmasry. The violation heap: A relaxed fibonacci-like heap. In My T. Thai and Sartaj Sahni, editors,Computing and Combinatorics, pages 479–488, Berlin, Heidelberg,

work page doi:10.1142/s0129054106004510
[4]

com/science/article/pii/S1570866712000834,doi:10.1016/j.jda.2012.04.014

URL:https://www.sciencedirect. com/science/article/pii/S1570866712000834,doi:10.1016/j.jda.2012.04.014. 10 Michael Fredman and Robert Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the ACM (JACM), 34(3):596–615,

work page doi:10.1016/j.jda.2012.04.014 2012
[5]

11 Michael Fredman and Dan Willard

doi:10.1145/ 28869.28874. 11 Michael Fredman and Dan Willard. Surpassing the information theoretic bound with fu- sion trees.Journal of computer and system sciences, 47(3):424–436,

work page arXiv
[6]

12 Michael L

doi:10.1016/ 0022-0000(93)90040-4. 12 Michael L. Fredman. On the efficiency of pairing heaps and related data structures.Journal of the ACM (JACM), 46(4):473–501, July 1999.doi:10.1145/320211.320214. Ivor van der Hoog, John Iacono, Eva Rotenberg, and Daniel Rutschmann 13 13 Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E. Tarjan. The...

work page doi:10.1145/320211.320214 1999
[7]

14 Michael L

doi:10.1007/BF01840439. 14 Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths.J. Comput. Syst. Sci., 48(3):533–551, June

work page doi:10.1007/bf01840439
[8]

15 Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan, and Jakub Tětek

doi: 10.1016/S0022-0000(05)80064-9. 15 Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan, and Jakub Tětek. Uni- versal optimality of dijkstra via beyond-worst-case heaps. InSymposium on Foundations of Computer Science (FOCS). IEEE, 2024.doi:10.1109/FOCS61266.2024.00125. 16 Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan. Rank-pairing...

work page doi:10.1016/s0022-0000(05)80064-9 2024
[9]

Arya and D

Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs. ICALP.2021.79. 19 John Iacono. Improved upper bounds for pairing heaps. InScandinavian Workshop on Algorithm Theory, pages 32–45. Springer, 2000.doi:10.5555/645900.672600. 20 John Iacono. Alternatives to splay trees with o(log n) worst-case access times. InSymposium on Discrete Algorith...

work page doi:10.4230/lipics 2021
[10]

21John Iacono.Distribution-sensitive data structures

URL:http://dl.acm.org/ citation.cfm?id=365411.365522. 21John Iacono.Distribution-sensitive data structures. PhD thesis,

work page arXiv
[11]

22 Haim Kaplan, Robert E

AAI3029688. 22 Haim Kaplan, Robert E. Tarjan, and Uri Zwick. Fibonacci heaps revisited.arXiv preprint arXiv:1407.5750, 2014.arXiv:1407.5750. 23 Donald E. Knuth.The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley,

work page arXiv 2014
[12]

Smooth heaps and a dual view of self-adjusting data structures

24 László Kozma and Thatchaphol Saranurak. Smooth heaps and a dual view of self-adjusting data structures. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 801–814, New York, NY, USA, June

2018
[13]

The art gallery problem is ∃R-complete

Association for Computing Machinery. URL:https://dl.acm.org/doi/10.1145/3188745.3188864, doi: 10.1145/3188745.3188864. 25 Seth Pettie. Towards a final analysis of pairing heaps. InSymposium on Foundations of Computer Science (FOCS), FOCS ’05, page 174–183, USA,

work page doi:10.1145/3188745.3188864
[14]

doi:10.1109/SFCS.2005.75

IEEE Computer Society. doi:10.1109/SFCS.2005.75. 26 Daniel Rutschmann. Sorting under partial information with optimal preprocessing time via unified bound heaps,

work page doi:10.1109/sfcs.2005.75 2005
[15]

Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps

URL:https://arxiv.org/abs/2604.12653,arXiv:2604.12653. 27 Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms.J. ACM, 31(2):245–281, March 1984.doi:10.1145/62.2160. 28 Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm.Journal of the ACM, 22(2):215–225, 1975.doi:10.1145/321879.321884. 29 Robert Endre...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/62.2160 1984
[16]

Optimization, approximation, and complexity classes,

URL: https://www.sciencedirect.com/science/article/pii/0022000079900424, doi:10.1016/ 0022-0000(79)90042-4. 30 Mikkel Thorup. On ac0 implementations of fusion trees and atomic heaps. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 699–707. ACM/SIAM, 2003.doi:10.1145/ 644108.644221. 14 Near-Optimal working-set heaps and their implications for Dij...

work page arXiv 2003
[17]

29 Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann

doi:10.1137/1.9781611978315.26. 32 Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann. Simpler Universally Optimal Dijkstra. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, European Symposium on Algorithms (ESA), volume 351 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 71:1–71:9, Dagstuhl, Germany,

work page doi:10.1137/1.9781611978315.26
[18]

33 Jean Vuillemin

Schloss Dagstuhl – Leibniz- Zentrum für Informatik.doi:10.4230/LIPIcs.ESA.2025.71. 33 Jean Vuillemin. A data structure for manipulating priority queues.Communications of the ACM, 21(4):309–315, April 1978.doi:10.1145/359460.359478. 34 J.W.J. Williams. Algorithm 232: Heapsort.Commun. ACM, 7(6):347–348, May

work page doi:10.4230/lipics.esa.2025.71 2025
[19]

doi:10.1145/512274.3734138

work page doi:10.1145/512274.3734138