TY - GEN

T1 - A Nearly-Tight Analysis of Multipass Pairing Heaps

AU - Sinnamon, Corwin

AU - Tarjan, Robert E.

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85165674255&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85165674255&partnerID=8YFLogxK

U2 - 10.1137/1.9781611977554.ch23

DO - 10.1137/1.9781611977554.ch23

M3 - Conference contribution

AN - SCOPUS:85165674255

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 535

EP - 548

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -