Technical Report, DIKU Report 97/25, Department of Computer Science, University of Copenhagen, 16 pages, October 1997.

A priority queue *Q* is a data structure that maintains a collection
of elements, each element having an associated priority drawn from a
totally ordered universe, under the operations ** Insert**, which
inserts an element into *Q*, and ** DeleteMin**, which deletes an
element with the minimum priority from *Q*. In this paper a
priority-queue implementation is given which is efficient with respect
to the number of block transfers or I/Os performed between the
internal and external memories of a computer. Let *B* and *M* denote
the respective capacity of a block and the internal memory measured in
elements. The developed data structure handles any intermixed
sequence of ** Insert** and ** DeleteMin** operations such that in every
disjoint interval of *B* consecutive priority-queue operations at most
*c* log_{M/B} (*N*/*M*) I/Os are performed, for some positive
constant *c*. These I/Os are divided evenly among the operations: if
*B* ≥ *c* log_{M/B} (*N*/*M*), one I/O is necessary for every
*B*/(*c*log_{M/B} (*N*/*M*))th operation and if *B* < *c* log_{M/B}
(*N*/*M*), *c*/*B*·log_{M/B} (*N*/*M*) I/Os are performed
per every operation. Moreover, every operation requires *O*(log_{2} *N*)
comparisons in the worst case. The best earlier solutions can only
handle a sequence of *S* operations with
*O*(sum_{i=1}^{S} (1/*B*)log_{M/B} (*N*_{i}/*M*)) I/Os, where
*N*_{i} denotes the number of elements stored in the data structure
prior to the *i*th operation, without giving any guarantee for the
performance of the individual operations.

diku-97-25.pdf (273 Kb)

**BIBT _{E}X entry**

@techreport{diku-97-25, author = "Gerth St{\o}lting Brodal and Jyrki Katajainen", institution = "Department of Computer Science, University of Copenhagen", month = "October", number = "DIKU Report 97/25", pages = "16", title = "Worst-Case Efficient External-Memory Priority Queues", year = "1997" }