2001-29: Adaptive Properties of Pairing Heaps

DIMACS TR: 2001-29

Adaptive Properties of Pairing Heaps

Authors: Amr Elmasry

ABSTRACT
We show that the pairing heap benefits from the presortedness in the input sequence, and sorts adaptively. In particular, we show that given an input sequence of size $n$ that is already sorted in ascending order from right to left, repeatedly deleting the smallest element, using the pairing heap operation, requires at most $7n$ comparisons. We also show that starting with any initial heap structure that has the property that the corresponding sequence of the heap is sorted in ascending order, at most $7n$ comparisons are required to produce the sorted sequence by repeatedly deleting the smallest element from the heap. This latter result implies an easy proof for Tarjan's sequential access theorem for splay trees, with a better bound of $3.5n$ rotations. Finally, experimental results are conducted, supporting the fact that the pairing heap is adaptive by comparing sorting using the pairing heap with Splaysort and Binomialsort.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-29.ps.gz

DIMACS Home Page