License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06091.5
URN: urn:nbn:de:0030-drops-7642
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/764/
Go to the corresponding Portal

Pettie, Seth

Towards a Final Analysis of Pairing Heaps

pdf-format:
06091.PettieSeth.ExtAbstract.764.pdf (0.2 MB)

Abstract

Fredman, Sedgewick, Sleator, and Tarjan proposed the
{em pairing heap}
as a self-adjusting, streamlined version of the Fibonacci heap.
It provably supports all priority queue operations in logarithmic
time and is known to be extremely efficient in practice.
However, despite its simplicity and empirical superiority,
the pairing heap is one of the few popular data structures
whose basic complexity remains open.
In this paper we prove that pairing heaps support the
deletemin operation in optimal logarithmic time and all other operations
(insert, meld, and decreasekey) in time
$O(2^{2sqrt{loglog n}})$. This result gives
the {em first} sub-logarithmic time bound for decreasekey
and comes close to the
lower bound of $Omega(loglog n)$ established by Fredman.

Pairing heaps have a well known but poorly understood relationship to
splay trees and, to date, the transfer of ideas has flowed in one direction:
from splaying to pairing. One contribution of this paper is a
new analysis that reasons explicitly with information-theoretic
measures. Whether these ideas could contribute to the analysis
of splay trees is an open question.


BibTeX - Entry

@InProceedings{pettie:DagSemProc.06091.5,
  author =	{Pettie, Seth},
  title =	{{Towards a Final Analysis of Pairing Heaps}},
  booktitle =	{Data Structures},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/764},
  URN =		{urn:nbn:de:0030-drops-7642},
  doi =		{10.4230/DagSemProc.06091.5},
  annote =	{Keywords: Data structure, heap, self-adjusting, amortized analysis}
}

Keywords: Data structure, heap, self-adjusting, amortized analysis
Collection: 06091 - Data Structures
Issue Date: 2006
Date of publication: 30.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI