# 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.

Online version

swat98ext.pdf (209 Kb)

DOI

10.1007/BFb0054359

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