Corey Sinnamon will present his FPO " Analysis of self-adjusting heaps" on Tuesday, 8/30/2022 at 3PM via Zoom. Zoom Link: [ https://princeton.zoom.us/my/sinnamon | https://princeton.zoom.us/my/sinnamon ] A copy of his thesis is available upon request. Please email gradinfo@cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. The members of Corey's committee are as follows: Examiners: Robert Tarjan (Advisor), Bernard Chazelle, and Maria Chudnovsky. Readers: Huacheng Yu and László Kozma (Freie Universität Berlin). 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( √ log log N2 √ 2 log2 log2 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 decreasekey; and O(1) for insert, meld, make-heap, and find-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 deletemin 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 Ozkan’s ¨ pure heap model, intended to capture all self-adjusting heaps. Slim and smooth heaps are the first known data structures to match Iacono and Ozkan’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.