Access Restriction

Author Fredman, Michael L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Fibonacci heaps ♦ Amortized complexity analysis ♦ Lower bounds ♦ Priority queues ♦ Self-adjusting data structures
Abstract The pairing heap is well regarded as an efficient data structure for implementing priority queue operations. It is included in the GNU C++ library. Strikingly simple in design, the pairing heap data structure nonetheless seems difficult to analyze, belonging to the genre of self-adjusting data structures. With its design originating as a self-adjusting analogue of the Fibonacci heap, it has been previously conjectured that the pairing heap provides constrant amortized time decrease-key operations, and experimental studies have supported this conjecture. This paper demonstrates, contrary to conjecture, that the pairing heap requires more than constant amortized time to perform decrease-key operations. Moreover, new experimental findings are presented that reveal detectable growth in the amortized cost of the decrease-key operation.Second, a unifying framework is developed that includes both pairing heaps and Fibonacci heaps. The parameter of interest in this framework is the storage capacity available in the nodes of the data structure for auxiliary balance information fields. In this respect Fibonacci heaps require log log $\textit{n}$ bits per node when $\textit{n}$ items are present. This is shown to be asymptotically optimal for data structures that achieve the same asymptotic performance bounds as Fibonacci heaps and fall within this framework.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 46
Issue Number 4
Page Count 29
Starting Page 473
Ending Page 501

Open content in new tab

   Open content in new tab
Source: ACM Digital Library