A linear potential function for pairing heaps

DOI10.1007/978-3-319-48749-6_36MaRDI QIDQ2958341zbMATH OpenOpenAlexFDO

Authors John Iacono, Mark Yagnatinsky

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06389

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We present the first potential function for pairing heaps with linear range. This implies that the runtime of a short sequence of operations is faster than previously known. It is also simpler than the only other potential function known to give amortized constant amortized time for insertion.

Recommendations

• The pairing heap: A new form of self-adjusting heap
• scientific article; zbMATH DE number 1617246
• On the efficiency of pairing heaps and related data structures
• Pairing heaps: the forward variant
• Rank-Pairing Heaps

Cites work

• A data structure for manipulating priority queues
• A linear potential function for pairing heaps
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• On the efficiency of pairing heaps and related data structures
• Pairing heaps with costless meld
• Rank-pairing heaps
• Self-adjusting binary search trees
• The pairing heap: A new form of self-adjusting heap

Cited in

(4)

• A linear potential function for pairing heaps
• scientific article; zbMATH DE number 1543353 (Why is no real title available?)
• Pairing heaps: the forward variant
• ATLAS: automated amortised complexity analysis of self-adjusting data structures

This page was built for publication: A linear potential function for pairing heaps

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