A Tight Analysis of Slim Heaps and Smooth Heaps

The smooth heap and the closely related slim heap are recently invented self-adjusting implementations of the heap (priority queue) data structure. They are simple to describe and efficient in practice. For both slim and smooth heaps, we derive the following tight bounds on 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, where n is the current number of items in the heap. These bounds are tight not only for slim and smooth heaps, but for any heap in Iacono and Özkan's pure heap model, intended to capture all “self-adjusting” heap implementations. Slim and smooth heaps are the first known data structures to match Iacono and Özkan's lower bounds while satisying the constraints of their model.