Analysis of Self-Adjusting Heaps

Abstract

We study the amortized efficiency of self-adjusting heap data structures. Heaps (also called priority queues) are fundamental data structures, and a great deal of work has been devoted to inventing efficient heaps and analyzing them. We prove new amortized bounds for pairing heaps, multipass pairing heaps, slim heaps, and smooth heaps. The pairing heap is a classic self-adjusting heap, known to be simple, robust, and efficient in practice. Despite decades of study, its exact efficiency is still unresolved. We prove new amortized bounds on the time per operation of the pairing heap: O(log n) amortized time for delete-min and delete; O(sqrt{log log N} 2^{sqrt{2log₂log₂ N}}) amortized time for insert, meld, and decrease-key; and O(1) time for make-heap and find-min. Here n is the current number of items in the heap, and N is an upper bound on n across all operations. The multipass pairing heap is a well-known variant of the pairing heap. We prove it satisfies amortized time bounds of O(log n) for delete-min and delete; O(log log n log log log n) for decrease-key; and O(1) for insert, meld, make-heap, and fifind-min. This is the first analysis in which both insert and delete-min take O(log n) amortized time. It matches the known lower bounds for all operations except decrease-key, and the bound for decrease-key comes close to the lower bound. We prove the same bounds for the lazy version of multipass pairing heaps, in which insert, meld, and decrease-key operations are done lazily. Again, these bounds are tight for all operations except decrease-key. The smooth heap and the closely related slim heap are much newer self-adjusting heaps. For these two heaps, we give a tight analysis of the amortized time per operation: O(log n) for delete-min and delete; O(log log n) for decrease-key; and O(1) for make-heap, find-min, insert, and meld. These bounds are tight not only for smooth and slim heaps, but for any heap in Iacono and Özkan's pure heap model, intended to capture all self-adjusting heaps. Slim and smooth heaps are the fifirst known data structures to match Iacono and Özkan's lower bounds and to satisfy the constraints of their model. We prove tight bounds for both eager and lazy versions of slim and smooth heaps.