Heap Construction - 50 Years Later

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 Q(N) worst-case time and performs at most 1.625N + o(N) element comparisons, 1.5N + o(N) element moves, N/B + O(N/M · lgN) cache misses, and 1.375N + 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 Theta(N) pointers. For a tuning parameter S, the idea is to divide the input into a top tree of size Theta(N/S) such that each of its leaves root a bottom tree of size Theta(S). When S = Theta(lgN/lglgN), 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.