In-place heap construction with optimized comparisons, moves, and cache misses
Authors:Jingsen Chen, Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Published in:Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 7464, Springer-Verlag (2012), 259–270
Full text:<pdf.gif>PDF (278 kB)  
DOI:10.1007/978-3-642-32589-2_25
Copyright:© Springer-Verlag
Abstract:We show how to build a binary heap in-place in linear time by performing ∼1.625n element comparisons, at most ∼2.125n element moves, and ∼n/B cache misses, where n is the size of the input array, B the capacity of the cache line, and ∼f(n) approaches f(n) as n grows. The same bound for element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their procedure requires Θ(n) pointers and does not have optimal cache behaviour. Our main idea is to mimic the Gonnet-Munro algorithm by converting a navigation pile into a binary heap. To construct a binary heap in-place, we use this algorithm to build bottom heaps of size Θ(lg n) and adjust the heap order at the upper levels using Floyd’s sift-down procedure. On another frontier, we compare different heap-construction alternatives in practice.
Related:<html.gif>HTML (Journal article)  <html.gif>HTML (Slides)  <html.gif>HTML (Source code)  
BibLATEX:
@inproceedings{CEEK2012C,
  author = {Jingsen Chen and Stefan Edelkamp and Amr Elmasry and Jyrki
    Katajainen},
  title = {In-place heap construction with optimized comparisons, moves, and
    cache misses},
  booktitle = {Proceedings of the 37th International Symposium on Mathematical
    Foundations of Computer Science},
  series = {Lecture Notes in Computer Science},
  volume = {7464},
  publisher = {Springer-Verlag},
  year = {2012},
  pages = {259--270},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2019-09-18.