Efficiency of self-adjusting heaps

DOI10.1145/3708989MaRDI QIDQ6907354zbMATH OpenFDO

Authors Corwin W. Sinnamon, Robert E. Tarjan

Publication date 3 November 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3708989

zbMATH Keywords

amortized analysisanalysis of algorithmsheapsmultipass pairing heappairing heappriority queueslim heapsmooth heap

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms (68W40)

Cites work

• A Back-to-Basics Empirical Study of Priority Queues
• A nearly-tight analysis of multipass pairing heaps
• A tight analysis of slim heaps and smooth heaps
• Fibonacci heaps and their uses in improved network optimization algorithms
• Greedy is an almost optimal deque
• Hollow heaps
• scientific article; zbMATH DE number 1617246 (Why is no real title available?)
• scientific article; zbMATH DE number 1670671 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• Improved bounds for multipass pairing heaps and path-balanced binary search trees
• On the efficiency of pairing heaps and related data structures
• Pairing heaps with O( n) decrease cost
• Smooth heaps and a dual view of self-adjusting data structures
• Space-efficient data structures, streams, and algorithms. Papers in honor of J. Ian Munro on the occasion of his 66th birthday
• The geometry of binary search trees
• The pairing heap: A new form of self-adjusting heap
• Toward optimal self-adjusting heaps
• Upper bounds for maximally greedy binary search trees

Cited in

(2)

• Strict Fibonacci heaps
• Fast and simple sorting using partial information

This page was built for publication: Efficiency of self-adjusting heaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6907354)