Worst-Case Efficient External-Memory Priority Queues

Gerth Stølting Brodal and Jyrki Katajainen

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

Abstract

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 logM/B (N/M) I/Os are performed, for some positive constant c. These I/Os are divided evenly among the operations: if Bc logM/B (N/M), one I/O is necessary for every B/(clogM/B (N/M))th operation and if B < c logM/B (N/M), c/BĚlogM/B (N/M) I/Os are performed per every operation. Moreover, every operation requires O(log2 N) comparisons in the worst case. The best earlier solutions can only handle a sequence of S operations with O(sumi=1S (1/B)logM/B (Ni/M)) I/Os, where Ni denotes the number of elements stored in the data structure prior to the ith operation, without giving any guarantee for the performance of the individual operations.

Online version

diku-97-25.pdf (273 Kb)

BIBTEX 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"
}