Heap construction—50 years later
Authors:Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Published in:The Computer Journal 60,5 (2017), 657–674
Full text:<pdf.gif>PDF (526 kB)  
DOI:10.1093/comjnl/bxw085
Copyright:© The British Computer Society
Abstract:We study the problem of constructing a binary heap in an array using only a small amount of additional space. Let N denote the size of the input, M the capacity of the cache, and B the width of the cache lines of the underlying computer, all measured as numbers of elements. We show that there exists an in-place heap-construction algorithm that runs in Θ(N) worst-case time and performs at most 1.625 N + o(N) element comparisons, 1.5 N + o(N) element moves, N / B + O(N / M · lg N) cache misses, and 1.375 N + o(N) branch mispredictions. The same bound for the number of element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their algorithm requires Θ(N) pointers. For a tuning parameter S, the idea is to divide the input into a top tree of size Θ(N / S) such that each of its leaves root a bottom tree of size Θ(S). When S = Θ(lg N / lg lg N), we can convert the bottom trees into heaps one by one by packing the extra space needed in a few words, and subsequently use Floyd’s sift-down procedure to adjust the heap order at the upper levels. In addition to our theoretical findings, we also compare different heap-construction alternatives in practice.
Related:<html.gif>HTML (Conference paper)  <html.gif>HTML (Slides)  <html.gif>HTML (Source code)  <tar.png>TAR (tar archive)  <html.gif>HTML (Errata)  
BibLATEX:
@article{EEK2017aJ,
  author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
  title = {Heap construction---50 years later},
  journaltitle = {The Computer Journal},
  volume = {60},
  number = {5},
  year = {2017},
  pages = {657--674},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2020-05-23.