Improved Upper Bounds for Pairing Heaps

2011/10/20 by Iacono, John · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1110.4428

Abstract

Pairing heaps are shown to have constant amortized time Insert and Meld, thus showing that pairing heaps have the same amortized runtimes as Fibonacci heaps for all operations but Decrease-key.

Cited by

• Heaps and Their Working Sets

Related

• A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion
• Pure Pairing Heaps
• Pairing Heaps with Costless Meld
• A Linear Potential Function for Pairing Heaps
• Pairing heaps: the forward variant