Why the Build Is Linear

The build sinks about $n/2$ internal nodes, and a sink runs at most the height of the tree, about $\log n$ steps, so a first estimate is $O(n\log n)$. But almost no node sinks the full height of the tree.

Sink cost and node height

A sink moves a node down one level per step and stops at the bottom, so the most a node can sink is the number of levels beneath it, its height. The root can sink about $\log n$ levels. A node one level above the bottom can sink at most once, and a node on the bottom level cannot sink at all. Only the nodes near the top can sink far, and there are few of them: one root, two nodes below it, four below those. Most of the nodes are near the bottom, and they sink zero steps or one step.

Total sink work

Start with a perfect tree, where every level is full. Let $k$ be the number of nodes on the bottom level, the ones that do no sinking at all. Each level up holds half as many nodes as the level below it, so counting upward from the bottom:

• $k$ nodes sink $0$ steps.
• $k/2$ nodes sink at most $1$ step.
• $k/4$ nodes sink at most $2$ steps.
• $k/8$ nodes sink at most $3$ steps.

The total work is at most the sum, over the levels, of the number of nodes on the level times the most steps each of them sinks:

$$\frac{k}{2}\cdot 1+\frac{k}{4}\cdot 2+\frac{k}{8}\cdot 3+\cdots =k\left(\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\cdots \right).$$

In the parentheses, the step count goes up by one each term, but the fraction of nodes halves. Call that sum $S$, and subtract half of it, term by term:

$$S-\frac{S}{2}=\frac{1}{2}+\left(\frac{2}{4}-\frac{1}{4}\right)+\left(\frac{3}{8}-\frac{2}{8}\right)+\cdots =\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots =1.$$

So $S/2=1$, and $S=2$. The build does at most about $2k$ steps.

Now, what is $k$? We do not need its exact value. The bottom level is part of the tree, so $k\le n$, and the build does at most $2k\le 2n$ steps:

$$\text{build cost}=O(n).$$

A heap’s tree is complete, but it is not always perfect: its last level may be only partly filled. Picture filling that level in. The result is a perfect tree of the same height $h$. Our complete tree has every level above the last full, which is $2^h-1$ nodes, plus at least one node on the last level, so $n\ge 2^h$. The filled-in tree has $2^{h+1}-1$ nodes, which is fewer than $2\cdot 2^h\le 2n$. Filling in gives every node at least as many levels beneath it as before, so the bound for the filled-in tree is at least the bound for ours. By the argument above, that bound is at most twice its node count, which is under $4n$. So the build is $O(n)$ for every heap, perfect or not.

This bottom-up build is due to Robert W. Floyd, who published it in 1964, the same year J. W. J. Williams published heapsort. It is often called heapify, or Floyd’s method.

The sortdown

The sortdown does not get the same saving. It runs $n-1$ turns, and every turn sinks from the root, which has the whole heap beneath it. So each sink can take up to about $\log n$ steps, and the sortdown is $O(n\log n)$. Add the $O(n)$ build, and heapsort is $O(n\log n)$.