A Survey on Priority Queues

Gerth Stølting Brodal

In Proc. Conference on Space Efficient Data Structures, Streams and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, volume 8066 of Lecture Notes in Computer Science, pages 150-163. Springer Verlag, Berlin, 2013.

Abstract

Back in 1964 Williams introduced the binary heap as a basic priority queue data structure supporting the operations Insert and ExtractMin in logarithmic time. Since then numerous papers have been published on priority queues. This paper tries to list some of the directions research on priority queues has taken the last 50 years.

Copyright notice

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

Online version

ianfest13.pdf (246 Kb)

DOI

10.1007/978-3-642-40273-9_11

Links

Slides

ianfest13.pdf (991 Kb), ianfest13.pptx (1555 Kb)

BIBTEX entry

@incollection{ianfest13,
  author = "Gerth St{\o}lting Brodal",
  booktitle = "Proc. Conference on Space Efficient Data Structures, Streams and Algorithms -- Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday",
  doi = "10.1007/978-3-642-40273-9_11",
  isbn = "978-3-642-40273-9",
  pages = "150-163",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "A Survey on Priority Queues",
  volume = "8066",
  year = "2013"
}