Near-Optimal Heaps and Dijkstra on Pointer Machines

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

Read Near-Optimal Heaps and Dijkstra on Pointer Machines by Ivor van der Hoog, John Iacono, Eva Rotenberg, Daniel Rutschmann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24134.txt.

Introduction

Van der Hoog, Iacono, Rotenberg, and Rutschmann build near-optimal working-set heaps on pointer machines, a deliberately spare model of computation. A working-set heap pops each item in time growing with the log of its working set, the items pushed while it waited. Word RAM designs already reach constant push and decrease-key costs, and the authors match constant push with inverse-Ackermann decrease-key on pointer machines. Dijkstra's algorithm then runs near-universally optimal on that model, with only a small additive overhead.

Catalog record

CREATORIvor van der Hoog, John Iacono, Eva Rotenberg, Daniel Rutschmann
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42179
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.24134

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near-Optimal Heaps and Dijkstra on Pointer Machines Ivor van der Hoog, John Iacono, Eva Rotenberg, Daniel Rutschmann 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 x_{i} ) pushes a new value x i x_{i} onto the heap, and DecreaseKey ( i i , v v ) decreases the value x i x_{i} to v v . A working-set heap is a heap that supports the x i ← x_{i}\leftarrow pop ( ) () operation in O ⁡ ( log ⁡ Γ ⁡ ( x i ) ) O(\log\Gamma(x_{i})) time where Γ ⁡ ( x i ) \Gamma(x_{i}) is the size of the working set : the number of elements that were pushed onto the heap while x i 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 ​ α ​ ( m ) ) O(m\,\alpha(m)) overhead compared to the optimal running time for distance ordering, where m m denotes the number of edges in the graph. IT University Copenhagen, [email protected] https://orcid.org/0009-0006-2624-0231 Université libre de Bruxelles, [email protected] https://orcid.org/0000-0001-8885-8172 IT University of Copenhagen, [email protected] https://orcid.org/0000-0001-5853-7909 Institute of Science and Technology Austria (ISTA), Klosterneuburg, [email protected] https://orcid.org/0009-0005-6838-2628 ccs Theory of computation Data structures design and analysis keywords Data structures, graph algorithms, amortized analysis † † runningtitle: Near-Optimal working-set heaps and their implications for Dijkstra † † runningauthor: Ivor van der Hoog, John Iacono, Eva Rotenberg, and Daniel Rutschmann † † copyright: Ivor van der Hoog, Eva Rotenberg, John Iacono, and Daniel Rutschmann † † funding: Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the VILLUM Foundation grant (VIL37507) “Efficient Recomputations for Changeful Problems” for supporting this work. Daniel Rutschmann is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (No. 101019564) . John Iacono is supported by the Fonds de la Recherche Scientifique — FNRS. 1 Introduction Heap data structures are one of the fundamental data structures in theoretical computer science, and there exist many heap implementations in the literature. Most of the heaps in the literature are based on heap-ordered trees, i.e. tree structures where the data stored in a node has a value that is not smaller than the value of the data stored in its parent. At a high level, a heap is a data structure used to repeatedly extract the minimum of a dynamic set. Formally, the Push operation adds a new data node onto the heap, and the pop operation extracts the minimum of the current heap. Heaps typically also support various other operations: MakeHeap creates a new heap and the Peek operation yields the minimum value in the heap without removing it. Another common and useful operation is the DecreaseKey operation which selects a current data node in the heap and replaces the data with a smaller value. The combination of DecreaseKey and Pop then allows for arbitrary deletions from the heap. Finally, heaps occasionally support the Meld operation which receives two heaps and returns a single heap containing all the data across the two heaps while maintaining its specific heap guarantees. We are interested in implementing heaps on a pointer machine — one of the most general models of computation, and one of the least-assuming generalizations of the RAM model used to analyze data structures. The classical pointer machine solution is a heap-ordered tree, which achieves logarithmic time for all aforementioned heap operations. Early examples are the implicit binary heaps of Williams [ 34 ] , the leftist heaps of Crane [ 5 ] and Knuth [ 23 ] , and the binomial heaps of Vuillemin [ 33 ] . Fredman and Tarjan introduced Fibonacci heaps [ 13 ] which achieved O(1) amortized time for all the above operations except for Pop , which requires O(\log n) amortized time where n is the number of data nodes in the heap. Fibonacci heaps had an immediate and famous application in Dijkstra’s algorithm for single-source shortest paths [ 6 ] . If Dijkstra’s algorithm is run on a graph with n nodes and m edges then, using a Fibonacci heap, the algorithm takes \Theta(m+n\log n) time, which is worst-case optimal. Since the introduction of Fibonacci heaps, a variety of other heaps with fast DecreaseKey have been introduced (see [ 3 ] for a full survey of priority queues): The Pairing heap [ 10 ] is a self-adjusting structure modeled after splay trees, whose asymptotic amortized DecreaseKey running time is unknown. Only an upper bound of O(2^{\sqrt{\log\log n}}) [ 25 ] and a lower bound of \Omega(\log\log n) [ 12 ] are known. The strict Fibonacci heap has worst-case rather than amortized running times [ 2 ] . Chan’s quake heaps were invented to be a simpler alternative to Fibonacci heaps with O(1) amortized time DecreaseKey [ 3 ] . Rank-pairing heaps [ 16 ] are another alternative to Fibonacci heaps with O(1) amortized time DecreaseKey but their structure is closer to the pairing heap. Violation heaps [ 9 ] , Hollow Heaps [ 17 ] , and Fibonacci Heaps revisited [ 22 ] are other variants with O(1) amortized time DecreaseKey . Slim and smooth heaps [ 18 ] have O(\log\log n) DecreaseKey , but are in the pointer-based model with constant indegree. Adaptive bounds. An adaptive heap supports the Pop operation in o(\log n) amortized time under specific circumstances, while the Push operation takes O(1) amortized time. Most existing heaps with adaptive bounds work without supporting the DecreaseKey operation: Iacono [ 19 ] shows that, on a pairing heap, x\leftarrow Pop () takes O(1+\log\Gamma(x)) time where \Gamma(x) is the number of data nodes that were pushed while x was on the heap. Elmasry [ 8 ] designs a heap on which x\leftarrow Pop () takes O(1+\log\Gamma^{\prime}(x)) time where \Gamma^{\prime}(x) is the number of data nodes that were pushed while x was on the heap and remain in the heap until x is popped. Elmasry, Farzan and Iacono [ 7 ] improve this to O(\min(\log\Gamma^{\prime}(x),\log\ell)) time where \Gamma^{\prime}(x) is defined in the same way and \ell is the number of data nodes that were pushed before x was pushed and that remain in the heap until x is popped. Rutschmann [ 26 ] designs a heap with the unified bound: x\leftarrow Pop () takes O(\min_{y}(1+\log(a(x,y))+\log(b(x,y))) time where y can be any data node that was already popped, a(x,y) is the number of push operations between Push ( x ) and Push (y) , and b(x,y) is the number of Pop operations between x\leftarrow

Read the complete text