## 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