Near-Optimal Heaps and Dijkstra on Pointer Machines
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915960725700608 |
|---|---|
| author | van der Hoog, Ivor Iacono, John Rotenberg, Eva Rutschmann, Daniel |
| author_facet | van der Hoog, Ivor Iacono, John Rotenberg, Eva Rutschmann, Daniel |
| contents | 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 Γ(x_i) )$ time where $Γ(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 \, α(m))$ overhead compared to the optimal running time for distance ordering, where $m$ denotes the number of edges in the graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24134 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Heaps and Dijkstra on Pointer Machines van der Hoog, Ivor Iacono, John Rotenberg, Eva Rutschmann, Daniel Data Structures and Algorithms 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 Γ(x_i) )$ time where $Γ(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 \, α(m))$ overhead compared to the optimal running time for distance ordering, where $m$ denotes the number of edges in the graph. |
| title | Near-Optimal Heaps and Dijkstra on Pointer Machines |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.24134 |