An in-place priority queue with O(1) time for push and lg n + O(1) comparisons for pop
Authors:Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Published in:Proceedings of the 10th International Computer Science Symposium in Russia, Lecture Notes in Computer Science 9139, Springer-Verlag (2015), 1-15
Full text:<pdf.gif>PDF (307 kB)  
DOI:10.1007/978-3-319-20297-6_14
Copyright:© Springer International Publishing Switzerland
Abstract:An in-place priority queue is a data structure that is stored in an array, uses constant extra space in addition to the array elements, and supports the operations top (find-min), push (insert), and pop (delete-min). In this paper we introduce an in-place priority queue, for which top and push take O(1) worst-case time, and pop takes O(lg n) worst-case time and involves at most lg n + O(1) element comparisons, where n denotes the number of elements currently in the data structure. The achieved bounds are optimal to within additive constant terms for the number of element comparisons, hereby solving a long-standing open problem. Compared to binary heaps, we surpass the comparison bound for pop and the time bound for push. Our data structure is similar to a binary heap with two crucial differences:
  1. To improve the comparison bound for pop, we reinforce a stronger heap order at the bottom levels of the heap such that the element at any right child is not smaller than that at its left sibling.
  2. To speed up push, we buffer insertions and allow O(lg2 n) nodes to violate heap order in relation to their parents.
Related:<html.gif>HTML (Journal article)  <html.gif>HTML (Technical report)  
BibLATEX:
@inproceedings{EEK2015C,
  author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
  title = {An in-place priority queue with $O(1)$ time for push and $\lg{} n +
    O(1)$ comparisons for pop},
  booktitle = {Proceedings of the 10th International Computer Science Symposium
    in Russia},
  series = {Lecture Notes in Computer Science},
  volume = {9139},
  publisher = {Springer-Verlag},
  year = {2015},
  pages = {1--15},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 17.05.2017.