Worst-Case Efficient External-Memory Priority Queues

Gerth Stølting Brodal and Jyrki Katajainen

In Proc. 6th Scandinavian Workshop on Algorithm Theory, volume 1432 of Lecture Notes in Computer Science, pages 107-118. Springer Verlag, Berlin, 1998.

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.

Copyright notice

© Springer-Verlag Berlin Heidelberg 1998. All rights reserved.

Online version

swat98ext.pdf (209 Kb)

DOI

10.1007/BFb0054359

Links

Slides

swat98ext.pdf (147 Kb)

BIBTEX entry

@incollection{swat98ext,
  author = "Gerth St{\o}lting Brodal and Jyrki Katajainen",
  booktitle = "Proc. 6th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/BFb0054359",
  isbn = "978-3-540-64682-2",
  pages = "107-118",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Worst-Case Efficient External-Memory Priority Queues",
  volume = "1432",
  year = "1998"
}

Other versions