筛选法建堆

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

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

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