Gonzalo Navarro, Rodrigo Paredes, Patricio Poblete, and Peter Sanders
The Quickheap (QH) is a recent data structure for implementing priority queues
which has proved to be simple and efficient in practice. It has also been
to offer logarithmic expected amortized complexity for all of its operations.
Yet, this complexity holds only when keys inserted and deleted are uniformly
distributed over the current set of keys. This assumption is in
many cases difficult to verify, and does not hold in some important
applications such as implementing some minimum spanning tree algorithms using
priority queues. In this paper we introduce an elegant model called a
Leftmost Skeleton Tree (LST) that reveals the connection between QHs and
randomized binary search trees, and allows us to define Randomized QHs.
We prove that these offer logarithmic expected amortized complexity for all
operations regardless of the input distribution.
We also use LSTs in connection to a-balanced trees to achieve a
a-Balanced QH that offers worst-case amortized logarithmic time
bounds for all the operations. Both variants are much more robust than the
We show experimentally that randomized QHs behave almost as efficiently as
QHs on random inputs, and that they retain their good performance on inputs
where that of QHs degrades.