Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan [ 8 ], it has been an open question whether this or any other simple “self-adjusting” heap supports decrease-key operations in \(\mathrm{O}(\log\log n)\) time, where \(n\) is the number of heap items. Using powerful new techniques, we answer this question in the affirmative. We prove that both slim and smooth heaps, recently introduced self-adjusting heaps, support heap operations in the following amortized time bounds: \(\mathrm{O}(\log n)\) for delete-min and delete, \(\mathrm{O}(\log\log n)\) for decrease-key, and \(\mathrm{O}(1)\) for all other heap operations, including insert and meld, where \(n\) is the number of heap items that are eventually deleted: Items inserted but never deleted do not count in the bounds. We also analyze the multipass pairing heap, a variant of pairing heaps. For this heap implementation, we obtain the same bounds except for decrease-key, for which our bound is \(\mathrm{O}(\log\log n\cdot\log\log\log n)\) , where again items that are never deleted do not count in \(n\) . Our bounds significantly improve the best previously known bounds for all three data structures. For slim and smooth heaps our bounds are tight, since they match lower bounds of Iacono and Özkan [ 13 ].

The pairing heap, introduced by Fredman et al. [3], is a self-adjusting heap data structure that is both simple and efficient. A variant introduced in the same paper is the multipass pairing heap. Standard pairing heaps do just two linking passes during delete-min, a pairing pass and an assembly pass. In contrast, multipass pairing heaps do repeated pairing passes, in which nodes are linked in adjacent pairs, until only a minimum-key node remains.

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.

The smooth heap is a recently introduced self-adjusting heap [Kozma, Saranurak, 2018] similar to the pairing heap [Fredman, Sedgewick, Sleator, Tarjan, 1986]. The smooth heap was obtained as a heap-counterpart of Greedy BST, a binary search tree updating strategy conjectured to be instance-optimal [Lucas, 1988], [Munro, 2000]. Several adaptive properties of smooth heaps follow from this connection; moreover, the smooth heap itself has been conjectured to be instance-optimal within a certain class of heaps. Nevertheless, no general analysis of smooth heaps has existed until now, the only previous analysis showing that, when used in sorting mode (n insertions followed by n delete-min operations), smooth heaps sort n numbers in O(nlg n) time. In this paper we describe a simpler variant of the smooth heap we call the slim heap. We give a new, self-contained analysis of smooth heaps and slim heaps in unrestricted operation, obtaining amortized bounds that match the best bounds known for self-adjusting heaps. Previous experimental work has found the pairing heap to dominate other data structures in this class in various settings. Our tests show that smooth heaps and slim heaps are competitive with pairing heaps, outperforming them in some cases, while being comparably easy to implement.

We present a space-efficient data structure using O(n log n) bits that represents a distributive lattice on n elements and supports finding meets and joins in O(log n) time. Our data structure extends the ideal tree structure of Habib and Nourine which occupies O(n log n) bits of space and requires O(m) time to compute a meet or join, where m depends on the specific lattice and may be as large as n – 1. We also give an encoding of a distributive lattice using bits, which is very close to the information theoretic lower bound. This encoding can be created or decompressed in O(n log n) time.