An experimental study of priority queues in external memory

In this paper we compare the performance of eight different priority queue implementations: four of them are explicitly designed to work in an external-memory setting, the others are standard internal-memory queues available in the LEDA library~\cite{leda}. Two of the external-memory priority queues are obtained by engineering known internal-memory priority queues with the aim of achieving effective performance on external storage devices (i.e., Radix heaps~\cite{Ahuja-et-al} and array heaps~\cite{Thorup}). Our experimental framework includes some simple tests, like random sequences of insert or delete-minimum operations, as well as more advanced tests consisting of intermixed sequences of update operations and ``application driven'' update sequences originated by simulations of Dijkstra's algorithm on large graph instances. Our variegate spectrum of experimental results gives a good picture of the features of these priority queues, thus being helpful to anyone interested in the use of such data structures on very large data sets