 Bottom-up heap construction

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\ge 1}\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.