= Bottom-up heap construction
{title2=$\sum_{h\ge1}\lfloor n/2^h\rfloor<n$}
Construct a <binary heap> from an <array> by processing internal nodes backwards, applying <sift down> at each. The <complete binary tree> shape ensures that the subtrees below the current node have already been repaired. The number of nodes whose height is at least $h$ is at most $\lfloor n/2^h\rfloor$, so charging each repair by its height gives total work at most a constant multiple of $n+\sum_{h\ge1}\lfloor n/2^h\rfloor<2n$. The construction takes $\Theta(n)$ time in either heap orientation, whereas inserting entries separately has an $O(n\log n)$ worst-case bound.
Back to article page
