# Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines

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

- Archive id: arxiv:2604.24134
- Published: 2026-04-27
- arXiv: https://arxiv.org/abs/2604.24134
- Source URL: https://arxiv.org/abs/2604.24134
- PDF: https://arxiv.org/pdf/2604.24134
- Provenance: arxiv

## 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 Γ(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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.