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