堆排序

首先这里指的二叉堆，是一层一层铺的，比较近似满二叉树。所以树的高度是被控制到 \(O(\log n)\) 的，从而删除堆顶时有一个平凡的 \(O(\log n)\) 的复杂度。

这里如果专门问建堆的复杂度，可能就是要你知道这里存在一个线性的复杂度：从底向上的建堆。这样会牺牲一点在线性，即 \(n\) 要先固定。 从 \(n\) 往 \(1\) 跑，每次合并自己的两个子树。于是每次合并的复杂度是自己作根的子树的高度。

从排序不等式的角度来说，这种算法就是让小的配大的，从而使得总和最小。

不妨先把 \(n\) 放大到最接近的二的幂次左右。

复杂度为 \(1\) 的，实际上占了 \(n/2\) 个结点；复杂度能达到 \(\log n\) 的，实际上只有 \(1\) 个结点（根结点）。

形式化地来说，大致形状是

\[ \sum\limits_{k=1}^{\log n}2^{k-1}\cdot(\log n -k) \]

或者

\[ T(n) = \frac{n}{2} + T(n/2) + \frac{n}{2} \]

其中前面一个 \(n/2\) 是最底层产生的复杂度，后面 \(T(n/2) + n/2\) 是剩下的上层点产生的复杂度。

于是 \(T(n) = O(n)\)。

对比来说，朴素的从前往后建堆，从排序不等式的角度来说，其实就是选择了让大的配大的，从而。即，对于底层的 \(n/2\) 个结点，他们全都要跑 \(O(\log n)\) 的复杂度，从而这里就直接达到 \(O(n\log n)\) 了。