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.gif>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.gif>HTML (Conference paper)  <html.gif>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},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2017-08-01.