Worst-Case Efficient Priority Queues

Gerth Stølting Brodal

In Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 52-58, 1996.

Abstract

An implementation of priority queues is presented that supports the operations MakeQueue, FindMin, Insert, Meld and DecreaseKey in worst case time O(1) and DeleteMin and Delete in worst case time O(log n). The space requirement is linear. The data structure presented is the first achieving this worst case performance.

Copyright notice

Copyright © 1996 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

Online version

soda96.pdf (208 Kb)

DOI

doi.acm.org/10.1145/313852.313883

Slides

soda96.pdf (144 Kb)

BIBTEX entry

@inproceedings{soda96,
  author = "Gerth St{\o}lting Brodal",
  booktitle = "Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "doi.acm.org/10.1145/313852.313883",
  isbn = "0-89871-366-8",
  pages = "52-58",
  title = "Worst-Case Efficient Priority Queues",
  year = "1996"
}