2026-08-16T00:49:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:764 2024-03-06T11:06:44Z ddc:004 open_access

Towards a Final Analysis of Pairing Heaps Pettie, Seth Data structure heap self-adjusting amortized analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Seth Pettie 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06091.5 urn:nbn:de:0030-drops-7642 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.5 eng https://creativecommons.org/licenses/by/4.0/legalcode