Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time

Gerth Stølting Brodal, Jesper Sindahl Nielsen, and Jakob Truelsen

In Proc. 14th International Workshop on Algorithms and Data Structures, volume 9214 of Lecture Notes in Computer Science, pages 1-12. Springer Verlag, Berlin, 2015.

Abstract

The binary heap of Williams (1964) is a simple priority queue characterized by only storing an array containing the elements and the number of elements n - here denoted a strictly implicit priority queue. We introduce two new strictly implicit priority queues. The first structure supports amortized O(1) time Insert and O(log n) time ExtractMin operations, where both operations require amortized O(1) element moves. No previous implicit heap with O(1) time Insert supports both operations with O(1) moves. The second structure supports worst-case O(1) time Insert and O(log n) time (and moves) ExtractMin operations. Previous results were either amortized or needed O(log n) bits of additional state information between operations.

Copyright notice

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

Online version

wads15.pdf (322 Kb)

DOI

10.1007/978-3-319-21840-3_8

Links

BIBTEX entry

@incollection{wads15,
  author = "Gerth St{\o}lting Brodal and Jesper Sindahl Nielsen and Jakob Truelsen",
  booktitle = "Proc. 14th International Workshop on Algorithms and Data Structures",
  doi = "10.1007/978-3-319-21840-3_8",
  pages = "1-12",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time",
  volume = "9214",
  year = "2015"
}

Other versions