Heaps and Their Working Sets
2026-07-27 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study special kinds of heaps—data structures that help organize information—that have better performance in real-life situations than worst-case scenarios suggest. They show that most ways to measure this improved performance, called working-set bounds, are basically the same, except for one stronger measure called the stack-like bound. Then, they build the first heap that meets this stronger stack-like bound while still allowing very fast key updates and insertions. This work helps unify theory and offers a new, efficient heap design.
heapworking-set boundstack-like boundamortized analysisdecrease-keyinsert operationdata structurebeyond worst-caselog-star function
Authors
Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert E. Tarjan
Abstract
We construct a heap with strong beyond-worst-case performance guarantees and explore the analysis of such heaps. First, we unify existing notions of the working-set bound for heaps by proving that essentially all of them are equivalent - with the notable exception of the so-called stack-like bound, which is strictly stronger. This equivalence simplifies the theoretical landscape and extends the range of applications of heaps with working-set bounds. Second, we present the first heap implementation that has the amortized stack-like bound and supports $\mathcal O(1)$-time decrease-key and $o(\log^*n)$-time insert.