2026-08-25T18:47:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27181 2026-08-25T13:18:17Z ddc:004 open_access

Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines van der Hoog, Ivor Iacono, John Rotenberg, Eva Rutschmann, Daniel Data structures graph algorithms amortized analysis 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 ← pop() operation in O(log Γ(x_i)) time where Γ(x_i) is the size of the 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ivor van der Hoog and John Iacono and Eva Rotenberg and Daniel Rutschmann 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.45 urn:nbn:de:0030-drops-271814 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.45 eng https://creativecommons.org/licenses/by/4.0/legalcode