  Since the invention of the pairing heap by Fredman et al., it has been an
open question whether this or any other simple "self-adjusting" heap supports
decrease-key operations on $n$-item heaps in $O(\log\log n)$ time. Using
powerful new techniques, we answer this question in the affirmative. We prove
that both slim and smooth heaps, recently introduced self-adjusting heaps,
support heap operations on an $n$-item heap in the following amortized time
bounds: $O(\log n)$ for delete-min and delete, $O(\log\log n)$ for
decrease-key, and $O(1)$ for all other heap operations, including insert and
meld. We also analyze the multipass pairing heap, a variant of pairing heaps.
For this heap implementation, we obtain the same bounds except for
decrease-key, for which our bound is $O(\log\log n \log\log\log n)$. Our bounds
significantly improve the best previously known bounds for all three data
structures. For slim and smooth heaps our bounds are tight, since they match
lower bounds of Iacono and Ozkan; for multipass pairing heaps our bounds are
tight except for decrease-key, which by the lower bounds of Fredman and Iacono
and \"Ozkan must take $O(\log\log n)$ amortized time if delete-min takes
$O(\log n)$ time.

Data Structures and Algorithms