Stronger Quickheaps
Gonzalo Navarro, Rodrigo Paredes, Peter Sanders, and Patricio V. Poblete
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 shown 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 alpha-balanced trees to achieve a
practical alpha-Balanced QH that offers worst-case amortized
logarithmic time bounds for all the operations. Both variants are
much more robust than the original QHs.
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.