Heaps and Their Working Sets

Bernhard Haeupler; Richard Hlad\'ik; Robert E. Tarjan; V\'aclav Rozho\v{n}

REVIEW 2 major objections 8 minor 33 references

Heaps and Their Working Sets

T0 review · 2 major / 8 minor · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Almost all working-set heap bounds are the same amortized guarantee; only the stack-like bound is strictly stronger, and a new heap achieves it with constant decrease-key.

desk verdict Clean unification of working-set heap bounds plus the first stack-like heap with true O(1) decrease-key; the delicate charging looks sound on a close read. read the letter →

arxiv 2607.24621 v1 pith:PI7P52LV submitted 2026-07-27 cs.DS

Bernhard Haeupler , Richard Hladík , Václav Rozhoň , Robert E. Tarjan This is my paper · ORCID

classification cs.DS MSC 68P0568Q25

keywords heapspriorityqueuesworking-setboundstack-likepropertydecrease-keyamortizedanalysisbeyond-worst-casedatastructures

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Heaps are usually judged by worst-case time, yet many algorithms only need good behavior when recent items are deleted often. The paper shows that the many natural definitions of this “working-set” guarantee—regular, insert-only, delete-only, touched-items, strong, and strict—are equivalent up to constants once costs are amortized, so any heap that meets one of them meets them all. The sole exception is the stack-like bound, which charges only the logarithm of how many still-present items are no older than the deleted one; that bound is strictly stronger. The authors then build the first comparison-model heap that attains the stack-like bound while still supporting decrease-key in constant amortized time and insert in time that is an arbitrarily slow iterated logarithm. The construction therefore simultaneously simplifies the theory and supplies a single data structure strong enough for the applications that previously demanded distinct heap variants.

What carries the argument

An inductive family of f-deque-like heaps built from quartermasters: each quartermaster stores consecutive items in bundles of size roughly f(w) inside an already-constructed f-deque-like warehouse, and a sequence of such quartermasters of preferred sizes w_i ≈ 2^{f(w_{i+1})} is kept balanced by FixTooBig/FixTooSmall moves that amortize to O(1) per item.

What would settle it

Exhibit an infinite family of insert/delete sequences on which every heap obeying one of the six working-set definitions still pays ω(n) total extract cost while a stack-like heap pays O(n), or produce a concrete implementation whose FixTooBig/FixTooSmall phases force super-constant amortized work per push for some fixed iteration depth k.

Watch

Extended reading notes

Core claim

In the amortized comparison-model setting, six working-set-style heap properties that appear throughout the literature are equivalent up to constant factors while preserving the cost of every other operation; the stack-like property is strictly stronger, and there exists a heap realizing it together with O(1) decrease-key and O(log*^(k) n) insert for every fixed k.

Load-bearing premise

The charging argument that moves items between successive quartermasters costs only a constant per insertion, even after the o(w_i) size-error terms that appear while sizes are being repaired, must hold for every slow-growing f in the iteration.

Editorial extensions

If this is right

Any existing heap already known to satisfy one working-set variant can be re-analyzed to satisfy all six, immediately transferring prior application results that required a stronger-looking variant.
Dijkstra and topological heapsort that previously needed a specially constructed strong or strict working-set heap now run with any ordinary working-set heap.
A single comparison-model structure can serve both as a classical Fibonacci-style heap and as a stack, with deletion cost interpolating smoothly between the two regimes.
Further constant-factor applications of the same inductive step yield heaps whose additive insert overhead is any fixed-height iterated logarithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the equivalence is black-box, future papers can safely cite “a working-set heap” without re-proving which of the six formulations they need.
The same quartermaster layering may be portable to other multi-order structures (e.g., set-union or order-maintenance) that must keep both a temporal spine and a key-order heap.
If the constant-factor blow-up per induction step can be made independent of k, an inverse-Ackermann insert overhead would become plausible; the paper leaves that open.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two real results here. First, they show that the six working-set variants people have been carefully distinguishing (regular, touched-items, insert-only, delete-only, strong, strict) are amortized-equivalent up to constants, while stack-like is strictly stronger. That collapses a fragmented toolkit that recent Dijkstra and partial-info sorting papers were dancing around. Second, they give the first comparison-model heap that is amortized stack-like and still has O(1) decrease-key, with insert only O(log*(k) n) for any fixed k. Prior stack-like heaps either lacked fast decrease-key or were not known to have it; the working-set heaps with fast decrease-key stopped short of stack-like.

The equivalence half is short, clean potential redistribution (happy/unhappy items, 1/i^2 charges by insertion or deletion order). It is the kind of argument you wish someone had written five years ago. The construction is the heavier lift: recursive quartermasters over warehouses of bundles, preferred sizes w_i ≈ 2^{f(w_{i+1})}, FixTooBig/FixTooSmall, and a stack-to-deque black box. Invariants and potentials are spelled out; base case is Fibonacci plus a linked list.

The soft spot is exactly where the reader and the stress-test put it: the multi-level move charging in §3.3.4 (Claims 3.23–3.24, Lemmas 3.25–3.26). Segment cutting is terse, and o(w_i) error terms have to stay controlled for slow f. On reading, the token accounting holds—segments start low and end high, only PushLeft grows F_i inside a segment, reverse moves are preceded by forward ones, small-i levels are O(1)—so this is verification risk, not a hole I can exhibit. Constant-factor blow-up per induction step is acknowledged (Remark 3.7); they correctly stop at fixed k. Section 5’s BST/splay sketches are secondary and known-style.

Citations are appropriate; self-cites to their Dijkstra/sorting work are the natural clients. No code, no Lean—normal for this venue and style.

This is for people who build or use beyond-worst-case heaps, or who need a clean reference for which working-set bound they can assume. I would bring it to reading group, cite the equivalence and the existence result, and send it to referees. The central claims hold as stated.

Referee Report

2 major / 8 minor

Summary. The paper makes two contributions on beyond-worst-case heaps in the comparison model. First (Section 4, Theorem 1.3), it proves that six working-set-style properties appearing in the literature (regular, touched-items, insert-only, delete-only, strong [Iacono], strict) are all equivalent up to constant factors in the amortized sense, while the stack-like property is strictly stronger (Lemma 1.4) and the size property strictly weaker (Theorem 4.14 and the following separation). The equivalences are proved by explicit potential-redistribution arguments (Theorems 4.10–4.11) that reassign O(1) potential per operation to pay for deletions of "unhappy" items. Second (Section 3, Theorem 3.3/Theorem 1.5), the paper constructs, for any fixed k, a heap with amortized Insert in O(log*(k) n), DecreaseKey in O(1), and ExtractMin/Delete in O(log s_x) (stack-like). The construction is inductive: starting from a Fibonacci heap augmented with a linked list (Lemma 3.6), each inductive step (Lemma 3.5) replaces the warehouse heap by the previously constructed f-deque-like heap, using "quartermasters" of preferred sizes w_i ≈ 2^{f(w_{i+1})} with bundles of size ≈ f(w_i), and a charging argument (Lemmas 3.25–3.26) to bound item migrations between adjacent quartermasters. Section 5 gives simple splay- and finger-tree-based working-set/stack-like heaps without fast DecreaseKey.

Significance. If correct, both results are of clear value. The equivalence theorem genuinely simplifies a fragmented landscape: prior work built special-purpose heaps for the strong and strict variants, and Theorem 1.3 retroactively shows any working-set heap suffices for those applications (e.g., the sorting-under-partial-information result of [Hae+26]). The proofs are short, self-contained, and black-box. The heap construction resolves the open problem stated in [EFI12] of a stack-like heap with fast DecreaseKey, at the cost of only an o(log* n) additive Insert overhead — a strong, concrete, and falsifiable bound. The construction is fully specified with explicit invariants, potentials, and charging lemmas, and the base case and inductive step are standard-comparison-model arguments with no fitted parameters (only the iteration depth k and a constant base size w_0 are free). The manuscript is also unusually honest about its limitations (amortized-only bounds, constant-factor blow-up per inductive level in Remark 3.7, the "ends empty" caveat in §5.1).

major comments (2)

[§3.3.4, Lemma 3.25] This lemma carries the entire amortization of the recursive construction (it is the only place where item oscillation across quartermaster boundaries is ruled out), yet its proof is the most compressed in the paper. The segment argument has a coherent invariant — within a segment starting with |F_i| < w_i/2 + o(w_i) and ending after a forward FixTooBig with |F_i| ≥ w_i − o(w_i), only PushLeft increases |F_i|, giving P_s − M_s ≥ w_i/2 − o(w_i) ≥ 0 for large fixed i — but several steps are left implicit and should be formalized: (a) the 'trimming' procedure (what exactly happens to a segment whose terminal FixTooBig is interleaved with FixTooSmall calls at other levels, and why segments without any FixTooBig contribute M_s = 0 and can be discarded); (b) the case split at segment start (Q_i previously empty vs. a preceding reverse move), including why |F_i| = o(w_i) in the empty case follow
[§3.3.3, Claim 3.22 (and its interaction with Claim 3.24)] The stack-like bound O(log s_x) for Delete relies on s_x ≥ |Q_{i−1}| ≥ w_{i−1}/2, i.e., on the size invariant holding at the moment the quartermaster-level Delete is invoked. The text acknowledges the invariant 'can be temporarily violated in the middle of an operation' and only proves |Q_i| = O(w_i) at all times (Claim 3.24). The argument is almost certainly fine — quartermaster Deletes happen at operation start, before FixTooSmall runs, so the invariant from the end of the previous operation applies up to an O(1) slack absorbed by the logarithm — but this ordering is never stated, and the chain f(w_i) = O(f(w_{i−1})) additionally uses f(n+1) = O(f(n)) from Remark 3.9 without saying so. Since this inequality is what converts the additive f(w_i) term into the stack-like bound, please make the invariant-at-operation-boundary assumption and the f-regularity steps explicit.

minor comments (8)

[Abstract] Typo: 'DecreaseKey ando(log ∗ n)-time insert' — missing space; also 'O(1)-time decrease-key' capitalization is inconsistent with the body.
[Remark 3.7] The claim that taking k = α(n) yields a '2^{O(α(n))}-deque-like heap' is asserted without justification and the phrasing is ambiguous (is the 2^{O(α(n))} a constant-factor blow-up per operation?). Either give a one-line derivation from the per-level constant-factor blow-up or soften the statement.
[Claim 3.16 vs. Lemma 3.11(4)] Notation mismatch: the lemma states BatchPop cost O(|L|) for the returned list L, while Claim 3.16 states O(|B|) for 'the bundle being returned'. Since a batch is a single bundle this is presumably the same quantity, but please unify the notation.
[§5.1] Two clarifications would help: (i) the individual weights 1/k² decrease over time as k grows, so the splay access lemma (stated for fixed weights) is being applied via a potential-decrease argument — one sentence making this explicit would preempt confusion; (ii) the 'provided the heap ends empty' restriction (negative potential of a non-empty tree) deserves a remark on whether it can be removed, e.g., by adding a constant to the potential.
[Definition 3.2] 'Distance of x to H.First ... plus one' is informal; since s_x is used quantitatively throughout (e.g., s_x ≥ |Q_{i−1}| ≥ w_{i−1}/2 in Claim 3.22), please define it as a count of items in the linked-list interval, consistent with Definition 1.1.
[§4, framing paragraph] The 'can be reanalysed' framing is appropriate and honestly stated; it would be worth one additional sentence noting that the redistribution in Theorems 4.10–4.11 is non-constructive (the potential assignment at time t depends on future deletion times), so the equivalence is about amortized cost accounting, not about an online rebalancing scheme.
[Figure 1] The figure would benefit from arrow labels or a caption sentence stating the direction of implication (strictly stronger → weaker) and where the strict separations are proved (Lemma 1.4, §4.3).
[General] Several line-break artifacts appear in the text ('W orking-set', 'A VL', 'T ouch-based', 'F raming', 'R oadmap') — presumably a PDF extraction issue, but please check the source. Also, ˜w_x (strict working-set size), w_i (preferred sizes), and w(x) (splay weights in §5.1) are three distinct uses of w; consider differentiating.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: self-contained comparison-model proofs with external base case and non-load-bearing application citations.

full rationale

The paper's two main results are proved by internal arguments that do not reduce to their inputs by construction. Theorem 1.3 equates six working-set notions via explicit amortization (potential redistribution in Theorems 4.10–4.11 and the hierarchy remarks); working-set/stack sizes are defined from the request sequence, not fitted. Theorem 3.3 is an inductive construction: base case is the standard Fibonacci heap plus a linked list (Lemma 3.6); the inductive step (Lemma 3.5) derives g-deque-like from f-deque-like by explicit preferred-size recurrences w_i ≈ 2^{f(w_{i+1})} and a segment charging argument (Lemmas 3.25–3.26). Self-citations (Hae+24b, Hae+26, etc.) appear only as motivation/applications of working-set heaps, not as premises inside the equivalence or construction proofs. No fitted parameters, no uniqueness theorem imported from the authors, and no renaming of a known empirical pattern. Honest non-finding.

Assumptions & free parameters 2 free parameters · 5 assumptions · 1 invented entities

Results sit in the standard comparison model with amortized analysis. The construction takes Fibonacci-heap bounds and an f-deque-like inductive hypothesis as given, then builds g via preferred sizes and potentials. No data-fitted constants; the only free choices are the induction depth k and a large enough base constant w_0.

free parameters (2)

k (iteration depth of log*) = any fixed positive integer
Fixed positive integer chosen by the user; each application of Lemma 3.5 worsens hidden constants, so k cannot grow with n without exponential constant blow-up (Remark 3.7).
w_0 (base preferred size) = large enough constant > 2
Chosen 'sufficiently large constant > 2' so that f-growth conditions of Claim 3.18 hold for the given f sequence.

assumptions (5)

domain assumption Comparison model: only pairwise key comparisons and pointer manipulation; time is number of such steps.
Stated throughout; all bounds are comparison-model amortized times.
standard math Fibonacci heaps support Insert/DecreaseKey in O(1) amortized and Delete in O(log n) amortized.
Base case Lemma 3.6; classical FT87 result used without re-proof.
standard math Amortized analysis via potentials is a valid cost model; additive O(1) per operation may be charged across Insert/Delete.
Used in Remarks 3.12, 4. framing, and all equivalence theorems.
ad hoc to paper Functions f in the sequence ½log n, log log n, log*, log**, … satisfy f(O(n))=O(f(n)) and are nondecreasing.
Remark 3.9; needed so warehouse overhead stays O(f(w_i)) under size drift.
ad hoc to paper No Merge operation is required; each item can store an explicit pointer to its current heap.
Remark 3.8; avoids disjoint-set hardness when items move across heaps.

invented entities (1)

Quartermaster (with warehouse of bundles) independent evidence
purpose: Inductive building block that exposes batch pop at both ends in O(1) per item while preserving f-deque-like Delete cost.
Defined in Lemma 3.11 / §3.2; engineering interface, not an external physical postulate. Independent evidence is the explicit implementation from an f-deque-like heap.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Heaps and Their Working Sets." pith.science (2026). https://pith.science/paper/PI7P52LV

@misc{pith2026260724621,
  author       = {Pith},
  title        = {Pith review of: Heaps and Their Working Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PI7P52LV}},
  note         = {Machine review of arXiv:2607.24621}
}

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.

Figures

Figures reproduced from arXiv: 2607.24621 by the authors.

**Figure 2.** Diagram of our basic heap construction: The data structure consists of warehouses of [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Diagram of our recursive heap construction. The data structure consists of quartermasters [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 11 canonical work pages

[1]

Fredman and Robert Endre Tarjan , title =

Michael L. Fredman and Robert Endre Tarjan , title =. J. 1987 , url =. doi:10.1145/28869.28874 , timestamp =

arXiv 1987
[2]

Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps , booktitle =

Bernhard Haeupler and Richard Hlad. Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps , booktitle =. 2024 , url =. doi:10.1109/FOCS61266.2024.00125 , timestamp =

arXiv 2024
[3]

Fast and Simple Sorting Using Partial Information , journal =

Bernhard Haeupler and Richard Hlad. Fast and Simple Sorting Using Partial Information , journal =. 2026 , url =. doi:10.1007/S00453-026-01387-3 , timestamp =

work page doi:10.1007/s00453-026-01387-3 2026
[4]

Improved Upper Bounds for Pairing Heaps , booktitle =

John Iacono , editor =. Improved Upper Bounds for Pairing Heaps , booktitle =. 2000 , url =. doi:10.1007/3-540-44985-X_5 , timestamp =

work page doi:10.1007/3-540-44985-x_5 2000
[5]

Fredman and Robert Sedgewick and Daniel Dominic Sleator and Robert Endre Tarjan , title =

Michael L. Fredman and Robert Sedgewick and Daniel Dominic Sleator and Robert Endre Tarjan , title =. Algorithmica , volume =. 1986 , url =. doi:10.1007/BF01840439 , timestamp =

doi:10.1007/bf01840439 1986
[6]

Soviet Mathematics Doklady , volume =

An algorithm for the organization of information , author =. Soviet Mathematics Doklady , volume =
[7]

Guibas and Robert Sedgewick , title =

Leonidas J. Guibas and Robert Sedgewick , title =. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978 , pages =. 1978 , url =. doi:10.1109/SFCS.1978.3 , timestamp =

doi:10.1109/sfcs.1978.3 1978
[8]

Daniel Dominic Sleator and Robert Endre Tarjan , title =. J. 1985 , url =. doi:10.1145/3828.3835 , timestamp =

arXiv 1985

Show all 33 references

[9]

Tarjan and Uri Zwick , title =

Thomas Dueholm Hansen and Haim Kaplan and Robert E. Tarjan and Uri Zwick , title =. 2017 , url =. doi:10.1145/3093240 , timestamp =

2017 doi
[10]

Worst-Case Efficient Priority Queues , booktitle =

Gerth St. Worst-Case Efficient Priority Queues , booktitle =. 1996 , url =

1996
[11]

Funnel Heap --

Gerth St. Funnel Heap --. Algorithms and Computation, 13th International Symposium,. 2002 , url =. doi:10.1007/3-540-36136-7_20 , timestamp =

2002 doi
[12]

A Priority Queue with the Working-set Property , author =. Int. J. Found. Comput. Sci. , volume =. 2006 , publisher =. doi:10.1142/S0129054106004510 , url =

2006 doi
[13]

A priority queue with the time-finger property , author =. J. Discrete Algorithms , volume =. 2012 , publisher =. doi:10.1016/j.jda.2012.04.014 , url =

2012 doi
[14]

Smooth Heaps and a Dual View of Self-Adjusting Data Structures , journal =

L. Smooth Heaps and a Dual View of Self-Adjusting Data Structures , journal =. 2020 , url =. doi:10.1137/18M1195188 , timestamp =

2020 doi
[15]

Ian Munro and Richard Peng and Sebastian Wild and Lingyi Zhang , title =

J. Ian Munro and Richard Peng and Sebastian Wild and Lingyi Zhang , title =. CoRR , volume =. 2019 , url =. 1908.00563 , timestamp =

2019 arXiv
[16]

Acta Informatica , volume =

Amr Elmasry and Arash Farzan and John Iacono , title =. Acta Informatica , volume =. 2013 , url =. doi:10.1007/S00236-013-0180-8 , timestamp =

2013 doi
[17]

A History of Distribution-Sensitive Data Structures , booktitle =

Prosenjit Bose and John Howat and Pat Morin , editor =. A History of Distribution-Sensitive Data Structures , booktitle =. 2013 , url =. doi:10.1007/978-3-642-40273-9\_10 , timestamp =

2013 doi
[18]

2023 , eprint =

Efficiency of Self-Adjusting Heaps , author =. 2023 , eprint =

2023
[19]

2015 , url =

Bernhard Haeupler and Siddhartha Sen and Robert Endre Tarjan , title =. 2015 , url =. doi:10.1145/2689412 , timestamp =

2015 doi
[20]

Simpler Optimal Sorting from a Directed Acyclic Graph , booktitle =

Ivor. Simpler Optimal Sorting from a Directed Acyclic Graph , booktitle =. 2025 , url =. doi:10.1137/1.9781611978315.26 , timestamp =

2025 doi
[21]

2011 , url =

Bernhard Haeupler and Siddhartha Sen and Robert Endre Tarjan , title =. 2011 , url =. doi:10.1137/100785351 , timestamp =

2011 doi
[22]

Alternatives to splay trees with O(log n) worst-case access times , booktitle =

John Iacono , editor =. Alternatives to splay trees with O(log n) worst-case access times , booktitle =. 2001 , url =

2001
[23]

2007 , publisher =

Dynamic optimality—almost , author =. 2007 , publisher =. doi:10.1137/S0097539705447347 , url =

2007 doi
[24]

Schmidt and Alan Siegel , title =

Richard Cole and Bud Mishra and Jeanette P. Schmidt and Alan Siegel , title =. 2000 , url =. doi:10.1137/S0097539797326988 , timestamp =

2000 doi
[25]

2000 , url =

Richard Cole , title =. 2000 , url =. doi:10.1137/S009753979732699X , timestamp =

2000 doi
[26]

Near-Optimal Heaps and Dijkstra on Pointer Machines , journal =

Ivor. Near-Optimal Heaps and Dijkstra on Pointer Machines , journal =. 2026 , url =. doi:10.48550/ARXIV.2604.24134 , eprinttype =. 2604.24134 , timestamp =

2026 doi arXiv
[27]

Simpler Universally Optimal Dijkstra , booktitle =

Ivor. Simpler Universally Optimal Dijkstra , booktitle =. 2025 , url =. doi:10.4230/LIPICS.ESA.2025.71 , timestamp =

2025 doi
[28]

CoRR , volume =

Daniel Rutschmann , title =. CoRR , volume =. 2026 , url =. doi:10.48550/ARXIV.2604.12653 , eprinttype =. 2604.12653 , timestamp =

2026 doi arXiv
[29]

2023 , eprint =

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps , author =. 2023 , eprint =

2023
[30]

2024 , eprint =

Fast and Simple Sorting Using Partial Information , author =. 2024 , eprint =

2024
[31]

Algorithmica , volume =

John Iacono and Stefan Langerman , title =. Algorithmica , volume =. 2005 , url =. doi:10.1007/S00453-004-1139-5 , timestamp =

2005 doi
[32]

1977 , publisher =

A programming and problem-solving seminar , author =. 1977 , publisher =

1977
[33]

Purely Functional Representations of Catenable Sorted Lists , booktitle =

Haim Kaplan and Robert Endre Tarjan , editor =. Purely Functional Representations of Catenable Sorted Lists , booktitle =. 1996 , url =. doi:10.1145/237814.237865 , timestamp =

1996

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.

[1] [1]

Fredman and Robert Endre Tarjan , title =

Michael L. Fredman and Robert Endre Tarjan , title =. J. 1987 , url =. doi:10.1145/28869.28874 , timestamp =

arXiv 1987

[2] [2]

Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps , booktitle =

Bernhard Haeupler and Richard Hlad. Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps , booktitle =. 2024 , url =. doi:10.1109/FOCS61266.2024.00125 , timestamp =

arXiv 2024

[3] [3]

Fast and Simple Sorting Using Partial Information , journal =

Bernhard Haeupler and Richard Hlad. Fast and Simple Sorting Using Partial Information , journal =. 2026 , url =. doi:10.1007/S00453-026-01387-3 , timestamp =

work page doi:10.1007/s00453-026-01387-3 2026

[4] [4]

Improved Upper Bounds for Pairing Heaps , booktitle =

John Iacono , editor =. Improved Upper Bounds for Pairing Heaps , booktitle =. 2000 , url =. doi:10.1007/3-540-44985-X_5 , timestamp =

work page doi:10.1007/3-540-44985-x_5 2000

[5] [5]

Fredman and Robert Sedgewick and Daniel Dominic Sleator and Robert Endre Tarjan , title =

Michael L. Fredman and Robert Sedgewick and Daniel Dominic Sleator and Robert Endre Tarjan , title =. Algorithmica , volume =. 1986 , url =. doi:10.1007/BF01840439 , timestamp =

doi:10.1007/bf01840439 1986

[6] [6]

Soviet Mathematics Doklady , volume =

An algorithm for the organization of information , author =. Soviet Mathematics Doklady , volume =

[7] [7]

Guibas and Robert Sedgewick , title =

Leonidas J. Guibas and Robert Sedgewick , title =. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978 , pages =. 1978 , url =. doi:10.1109/SFCS.1978.3 , timestamp =

doi:10.1109/sfcs.1978.3 1978

[8] [8]

Daniel Dominic Sleator and Robert Endre Tarjan , title =. J. 1985 , url =. doi:10.1145/3828.3835 , timestamp =

arXiv 1985