A Tight Analysis of Slim Heaps and Smooth Heaps

Corwin Sinnamon, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageAmerican English
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages549-567
Number of pages19
ISBN (Electronic)9781611977554
StatePublished - 2023
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period1/22/231/25/23

ASJC Scopus subject areas

  • Software
  • General Mathematics

Cite this