| 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 (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:
|
| Related: |  HTML (Journal article) 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},
}
|