Pairing heaps: the forward variant

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

15 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
Titel43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
RedacteurenIgor Potapov, James Worrell, Paul Spirakis
Plaats van productieWadern
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's14
ISBN van geprinte versie978-3-95977-086-6
DOI's
StatusGepubliceerd - 1 aug 2018
Evenement43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, Verenigd Koninkrijk
Duur: 27 aug 201831 aug 2018

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
Volume117
ISSN van geprinte versie1868-8969

Congres

Congres43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
LandVerenigd Koninkrijk
StadLiverpool
Periode27/08/1831/08/18

Vingerafdruk Duik in de onderzoeksthema's van 'Pairing heaps: the forward variant'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Dorfman, D., Kaplan, H., Kozma, L., & Zwick, U. (2018). Pairing heaps: the forward variant. In I. Potapov, J. Worrell, & P. Spirakis (editors), 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 [13] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 117). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2018.13