Toward Optimal Self-Adjusting Heaps
Amr Elmasry · ACM Transactions on Algorithms · 2017
We give a variant of the pairing heaps that achieves the following amortized costs: O (1) per find-min and insert , O (log log n ) per decrease-key and meld , O (log n ) per delete-min ; where n is the number of elements in the resulting heap on which the operation is performed. These bounds are the best known for any self-adjusting heap and match two lower bounds, one established by Fredman and the other by Iacono and Özkan, for a family of self-adjusting heaps that generalizes the pairing heaps but do not include our variant. We further show how to reduce the amortized cost for meld to be paid by the other operations, on the expense of increasing that of delete-min to O (log n + log log N ), where N is the total number of elements in the collection of heaps of the data structure (not just the heap under consideration by the operation).