A Nearly-Tight Analysis of Multipass Pairing Heaps

Corwin Sinnamon, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The pairing heap, introduced by Fredman et al. [3], is a self-adjusting heap data structure that is both simple and efficient. A variant introduced in the same paper is the multipass pairing heap. Standard pairing heaps do just two linking passes during delete-min, a pairing pass and an assembly pass. In contrast, multipass pairing heaps do repeated pairing passes, in which nodes are linked in adjacent pairs, until only a minimum-key node remains. We obtain the following amortized time bounds for operations on n-item multipass pairing heaps: O(log n) for delete-min and delete; O(log log n log log log n) for decrease-key; and O(1) for all other heap operations, including insert and meld. This is the first analysis giving an O(log n) bound for delete-min. Our analysis is tight for all operations except possibly decrease-key, for which Fredman [2] and separately Iacono and Özkan [6] proved an Ω(log log n) lower bound.

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages535-548
Number of pages14
ISBN (Electronic)9781611977554
StatePublished - 2023
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period1/22/231/25/23

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'A Nearly-Tight Analysis of Multipass Pairing Heaps'. Together they form a unique fingerprint.

Cite this