2022/08/24 by Corwin Sinnamon, Robert E. Tarjan, Robert Tarjan +2 · 1 citation
Computer Science · Mathematics · #68P05 (Primary) 68W40 (Secondary) #Algorithm #Algorithms and Data Compression #Amortized analysis #Arithmetic #Binary logarithm #Binary number #Binary tree #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #Data structure #Discrete mathematics #E.1 #E.2 #F.2.2 #FOS: Computer and information sciences #Heap (data structure) #Mathematics #Natural Language Processing Techniques #Operating system #Pairing #Priority queue #Programming language #Queue #Software Testing and Debugging Techniques #acm:68P05 #acm:68W40 #cs.DS #msc:68P05 #msc:68W40
paper · pdf · doi:10.48550/arxiv.2208.11791
published in arXiv (Cornell University) (Cornell University) · 13 pages, 1 figure, submitted to SOSA 2023
arxiv created 2022/08/24 · openalex publication_date 2022/08/24 · arxiv updated 2022/08/26 · openalex created_date 2022/08/27 · openalex updated_date 2026/08/06
The pairing heap is a simple "self-adjusting" implementation of a heap (priority queue). Inserting an item into a pairing heap or decreasing the key of an item takes O(1) time worst-case, as does melding two heaps. But deleting an item of minimum key can take time linear in the heap size in the worst case. The paper that introduced the pairing heap proved an O(log n) amortized time bound for each heap operation, where n is the number of items in the heap or heaps involved in the operation, by charging all but O(log n) of the time for each deletion to non-deletion operations, O(log n) to each. Later Iacono found a way to reduce the amortized time per insertion to O(1) and that of meld to zero while preserving the O(log n) amortized time bound for the other update operations. We give a simpler proof of Iacono's result with significantly smaller constant factors. Our analysis uses the natural representation of pairing heaps instead of the conversion to a binary tree used in the original analysis and in Iacono's.