Improved bounds for multipass pairing heaps and path-balanced binary search trees

DOI10.4230/LIPICS.ESA.2018.24arXiv1806.08692MaRDI QIDQ6303370FDOQ6303370

Authors: Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, Uri Zwick 

Publication date: 22 June 2018

Abstract: We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient "self-adjusting" 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. Path-balanced BSTs, proposed by Sleator (Subramanian, 1996), are a natural alternative to Splay trees (Sleator and Tarjan, 1983). In a path-balanced BST, whenever an item is accessed, the search path leading to that item is re-arranged 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(logncdotloglogn/logloglogn)$ time. For searching in path-balanced BSTs, Balasubramanian and Raman showed in 1995 the same amortized time bound of $O(logncdotloglogn/logloglogn)$, using a different argument. In this paper we show an explicit connection between the two algorithms and improve the two bounds to $Oleft(logncdot{2}^{lo{g}^{ast}n}cdotlo{g}^{ast}night)$, respectively $Oleft(logncdot{2}^{lo{g}^{ast}n}cdot(lo{g}^{ast}n{)}^{2}ight)$, where $lo{g}^{ast}(cdot)$ denotes the very slowly growing iterated logarithm function. These are the first improvements in more than three, resp. two decades, approaching in both cases the information-theoretic lower bound of $Omega(logn)$.

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

This page was built for publication: Improved bounds for multipass pairing heaps and path-balanced binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6303370)