筛选法建堆

这可能是本学期学习数据结构与算法课的最大收获，就是知道了还有线性建堆的方法。线性建堆可能也是有应用场景的，比如用$O(n)$的空间及时间复杂度，取出前$n/\log n$大的所有数。（？

算法描述

筛选法作用在一棵二叉树上，在不改变其形态、只交换其元素的情况下，使其满足堆的定义。所以无论使用二叉链表还是数组建立二叉树，都可以使用筛选法。并且这个方法不改变树的形态，不用担心深度增加之类的。

筛选法就是将所有非叶子节点，按照树上的祖孙关系（孙子在先，祖先在后）得到的一个拓扑序，进行如下操作：

（1）若这个叶子节点大于其每个儿子，跳过；

（2）否则将其与较大的那个儿子交换，直到满足（1）。

显然这个操作得到的是一个堆，下面证明这个操作的复杂度是$O(n)$的。

复杂度证明

考虑$n$层的完美二叉树，最坏情况下，第$k$层结点交换$(n-k)$次，第$k$层结点有$2^{k-1}$个。于是总交换次数为

$$\begin{aligned} & \sum_{k=1}^{n}(n-k)2^{k-1}\\ = & n\sum_{k=1}^{n}2^{k-1}-\sum_{k=1}^{n}k2^{k-1}\\ = & (n2^n-n)-(\sum_{k=1}^{n}2^{k-1}+\sum_{k=2}^{n}2^{k-1}+...+\sum_{k=n}^{n}2^{k-1})\\ = & (n2^n-n)-\Big[(2^n-2^0)+(2^n-2^1)+...+(2^n-2^{n-1})\Big]\\ = & (n2^n-n)-(n2^n-2^n+1)\\ = & 2^n - n - 1 \end{aligned} $$

是元素个数级别的。对其他的完全二叉树，不妨想象将其最后一层填充满，显然也是线性的时间复杂度。

这个算法不占用辅助空间，空间复杂度仅为原来的数组空间，是线性的。