Pairing heaps: the forward variant

Dani Dorfman, Haim Kaplan, László Kozma, Uri Zwick

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
26 Downloads (Pure)

Abstract

The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent performance in practice. The “magic” of pairing heaps lies in the restructuring that happens after the deletion of the smallest item. The resulting collection of trees is consolidated in two rounds: a left-to-right pairing round, followed by a right-to-left accumulation round. Fredman et al. showed, via an elegant correspondence to splay trees, that in a pairing heap of size n all heap operations take O(log n) amortized time. They also proposed an arguably more natural variant, where both pairing and accumulation are performed in a combined left-to-right round (called the forward variant of pairing heaps). The analogy to splaying breaks down in this case, and the analysis of the forward variant was left open. In this paper we show that inserting an item and deleting the minimum in a forward-variant pairing heap both take amortized time O(log n · 4 log n). This is the first improvement over the O(n) bound showed by Fredman et al. three decades ago. Our analysis relies on a new potential function that tracks parent-child rank-differences in the heap.

Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
EditorsIgor Potapov, James Worrell, Paul Spirakis
Place of PublicationWadern
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages14
ISBN (Print)978-3-95977-086-6
DOIs
Publication statusPublished - 1 Aug 2018
Event43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, United Kingdom
Duration: 27 Aug 201831 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume117
ISSN (Print)1868-8969

Conference

Conference43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
Country/TerritoryUnited Kingdom
CityLiverpool
Period27/08/1831/08/18

Keywords

  • Data structure
  • Pairing heap
  • Priority queue

Fingerprint

Dive into the research topics of 'Pairing heaps: the forward variant'. Together they form a unique fingerprint.

Cite this