Pairing heaps, scrambled pairing and square-root trees

Abstract

Fredman et al. have shown that the amortized cost for deleting the item with the minimum value from a pairing heap is O(√n), no matter how the pairing is done [M. Fredman, R. Sedgewick, D. Sleator, and R. Tarjan, The Pairing heap: a new form of self-adjusting heap, Algorithmica 1(1) (1986), pp. 111–129]. In this paper, this upper bound is shown to be realizable (indicating that their analysis is tight). More precisely, starting with any n-node heap, we consider an alternating sequence of the operations: delete-min and insert; and give a pairing strategy for which Θ(√n) is the amortized cost per delete-min, irrespective of the initial heap structure. More interesting is that, starting with any initial structure, the heap will converge after O(n ^1.5) operations to the same structure, which we call the square-root tree.

Keywords:

• algorithms
• data structures
• self-adjusting structures
• priority queues
• pairing heaps

2000 AMS Subject Classifications :

• 68P05
• 68W40

Acknowledgements

I would like to thank the anonymous referees for their constructive suggestions and comments, which not only improved the presentation of the paper but also helped with filling the gaps in it. A. Elmasry was supported by an Alexander von Humboldt Fellowship.