证明:
一棵完全二叉树上有 $\left\lceil{\log_2 n}\right\rceil$ 层,叶子结点没有结点了,所以叶子结点不需要 down,所以从 $\dfrac{n}{2}$ 开始 down,所以除了叶子结点,上面的所有结点的个数为 $\dfrac{n}{2}$,除去叶子结点,上面的最后一层结点就是 $\dfrac{n}{4}$。
所以:
\begin{equation}
\dfrac{n}{2} \times 1 + \dfrac{n}{4} \times 2 + \cdots + \dfrac{n}{2^{\left\lceil{\log_2 n}\right\rceil}} \times \left\lfloor{\log_2 n}\right\rfloor \\
= \left\lfloor{\log_2 h}\right\rfloor \sum ^ {\left\lceil{\log_2 n}\right\rceil} _ {h=1} \dfrac{n}{2^h} \\
= n(\dfrac{1}{2^2} + \dfrac{1}{2^3} + \dfrac{1}{2^4} + \cdots +\dfrac{1}{2^{\left\lceil{\log_2 n}\right\rceil}}) \\
= n \sum^{\left\lceil{\log_2 n}\right\rceil} _ {h = 2} 2^h\\
\end{equation}
那么上面的公式是不是 $\mathcal{O}(n)$ 的呢?
\begin{equation}
s = \dfrac{1}{2^2} + \dfrac{1}{2^3} + \dfrac{1}{2^4} + \cdots +\dfrac{1}{2^{\left\lceil{\log_2 n}\right\rceil}} \\
\ 2s = \dfrac{1}{2} + \dfrac{2}{2^2} + \dfrac{3}{2^3} + \cdots + \dfrac{\left\lceil{\log_2 n}\right\rceil}{2^{\left\lceil{\log_2 n}\right\rceil}} \\
\ 2s - s = s= \dfrac{1}{2} + \dfrac{1}{2^2} + \dfrac{1}{2^3} + \cdots + \dfrac{1}{2^{\left\lceil{\log_2 n}\right\rceil}}
\end{equation}
因为 s 是小于 $1$ 的,所以 $\sum\limits^{\left\lceil{\log_2 n}\right\rceil} _ {h = 2} 2^h < 1$,故建堆时间复杂度为 $\mathcal{O}(n)$。因此堆排序的时间复杂度为 $\mathcal{O}(n \log_2 n)$。
证毕。