| 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 (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 (Conference paper) HTML (Slides) HTML (Source code)  TAR (tar archive) 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},
}
|