| Optimizing binary heaps | |
| Authors: | Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen |
| Published in: | Theory of Computing Systems 61,2 (2017), 606–636 |
| Full text: |  PDF (370 kB) |
| DOI: | 10.1007/s00224-017-9760-2 |
| Copyright: | © Springer Science+Business Media New York |
| Abstract: | A priority queue—a data structure supporting, inter alia, the operations minimum (top), insert (push), and extract-min (pop)—is said to operate in-place if it uses O(1) extra space in addition to the n elements stored at the beginning of an array. Prior to this work, no in-place priority queue was known to provide worst-case guarantees on the number of element comparisons that are optimal up to additive constant terms for both insert and extract-min. In particular, for the standard implementation of binary heaps, insert and extract-min operate in logarithmic time while involving at most ⌈lg n⌉ and 2 lg n [could possibly be reduced to lg lg n + O(1) and lg n + log* n + O(1)] element comparisons, respectively. In this paper we propose a variant of a binary heap that operates in-place, executes minimum and insert in O(1) worst-case time, and extract-min in O(lg n) worst-case time while involving at most lg n + O(1) element comparisons. These efficiencies surpass lower bounds known for binary heaps, thereby resolving a long-standing theoretical debate. |
| Related: |  HTML (Conference paper) HTML (Technical report) |
| BibLATEX: | @article{EEK2017bJ,
author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
title = {Optimizing binary heaps},
journaltitle = {Theory of Computing Systems},
volume = {61},
number = {2},
year = {2017},
pages = {606--636},
}
|