Dorfman, Dani ;
Kaplan, Haim ;
Kozma, László ;
Pettie, Seth ;
Zwick, Uri
Improved Bounds for Multipass Pairing Heaps and PathBalanced Binary Search Trees
Abstract
We revisit multipass pairing heaps and pathbalanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient "selfadjusting" heap, introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. In the multipass variant (one of the original pairing heap variants described by Fredman et al.) the minimum item is extracted via repeated pairing rounds in which neighboring siblings are linked.
Pathbalanced BSTs, proposed by Sleator (cf. Subramanian, 1996), are a natural alternative to Splay trees (Sleator and Tarjan, 1983). In a pathbalanced BST, whenever an item is accessed, the search path leading to that item is rearranged into a balanced tree.
Despite their simplicity, both algorithms turned out to be difficult to analyse. Fredman et al. showed that operations in multipass pairing heaps take amortized O(log n * log log n / log log log n) time. For searching in pathbalanced BSTs, Balasubramanian and Raman showed in 1995 the same amortized time bound of O(log n * log log n / log log log n), using a different argument.
In this paper we show an explicit connection between the two algorithms and improve both bounds to O(log n * 2^{log^* n} * log^* n), respectively O(log n * 2^{log^* n} * (log^* n)^2), where log^* denotes the slowly growing iterated logarithm function. These are the first improvements in more than three, resp. two decades, approaching the informationtheoretic lower bound of Omega(log n).
BibTeX  Entry
@InProceedings{dorfman_et_al:LIPIcs:2018:9487,
author = {Dani Dorfman and Haim Kaplan and L{\'a}szl{\'o} Kozma and Seth Pettie and Uri Zwick},
title = {{Improved Bounds for Multipass Pairing Heaps and PathBalanced Binary Search Trees}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {24:124:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9487},
URN = {urn:nbn:de:0030drops94879},
doi = {10.4230/LIPIcs.ESA.2018.24},
annote = {Keywords: data structure, priority queue, pairing heap, binary search tree}
}
2018
Keywords: 

data structure, priority queue, pairing heap, binary search tree 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 