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)

BibL^{A}T_{E}X:

@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},
}