筛选法建堆

这可能是本学期学习数据结构与算法课的最大收获, 就是知道了还有线性建堆的方法. 线性建堆可能也是有应用场景的, 比如用$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} $$

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

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