We present a new connection between self-adjusting binary search trees (BSTs) and heaps,
two fundamental, extensively studied, and practically relevant families of data structures …

We introduce the hollow heap, a very simple data structure with the same amortized
efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min …

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 …

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 …

We improve the lower bound on the amortized cost of the decrease-key operation in the
pure heap model and show that any pure-heap-model heap (that has a\bigoh {\log n} …

We give a variant of the pairing heaps that achieves the following amortized costs: O (1) per
find-min and insert, O (log log n) per decrease-key and meld, O (log n) per delete-min; …

I declare that this document and the accompanying code has been composed by myself,
and describes my own work, unless otherwise acknowledged in the text. It has not been …

This chapter presents three algorithmically related data structures for implementing
meldable priority queues: binomial heaps, Fibonacci heaps, and pairing heaps. What these …

The pairing heap is a classical heap data structure introduced in 1986 by Fredman,
Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent …

This thesis studies a series of questions about dynamic algorithms which are algorithms for
quickly maintaining some information of an input data undergoing a sequence of updates …