heapify()
还有一个大名鼎鼎的非常重要的操作，就是 heapify() 了，它是一个很神奇的操作，
可以用 O(n) 的时间把一个乱序的数组变成一个 heap。
但是呢，heapify() 并不是一个 public API，看：
所以我们没有办法直接使用。
唯一使用 heapify() 的方式呢，就是使用
PriorityQueue(Collection<? extends E> c)
这个 constructor 的时候，人家会自动调用 heapify() 这个操作。
<span style="display:block;color:blue;">那具体是怎么做的呢？
哈哈源码已经暴露了：
从最后一个非叶子节点开始，从后往前做 siftDown().
因为叶子节点没必要操作嘛，已经到了最下面了，还能和谁 swap？
举个例子：
我们想把这个数组进行 heapify() 操作，想把它变成一个最小堆，拿到它的最小值。
那就要从 3 开始，对 3，7，5进行 siftDown().
Step 1.
尴尬 😅，3 并不用交换，因为以它为顶点的这棵小树已经满足了堆序性。
Step 2.
7 比它的两个孩子都要大，所以和较小的那个交换一下。
交换完成后；
Step 3.
最后一个要处理的就是 5 了，那这里 5 比它的两个孩子都要大，所以也和较小的那个交换一下。
换完之后结果如下，注意并没有满足堆序性，因为 4 还比 5 小呢。
所以接着和 4 换，结果如下：
这样整个 heapify() 的过程就完成了。
好了难点来了，为什么时间复杂度是 O(n) 的呢？
怎么计算这个时间复杂度呢？
其实我们在这个过程里做的操作无非就是交换交换。
那到底交换了多少次呢？
没错，交换了多少次，时间复杂度就是多少。
那我们可以看出来，其实同一层的节点最多交换的次数都是相同的。
那么这个总的交换次数 = 每层的节点数 * 每个节点最多交换的次数
这里设 k 为层数，那么这个例子里 k=3.
每层的节点数是从上到下以指数增长：
$$\ce{1, 2, 4, ..., 2^{k-1}}$$
每个节点交换的次数，
从下往上就是：
0, 1, ..., k-2, k-10,1,...,k−2,k−1
那么总的交换次数 S(k) 就是两者相乘再相加：
S(k) = \left(2^{0} *(k-1) + 2^{1} *(k-2) + ... + 2^{k-2} *1 \right)S(k)=(20∗(k−1)+21∗(k−2)+...+2k−2∗1)
这是一个等比等差数列，标准的求和方式就是错位相减法。
那么
2S(k) = \left(2^{1} *(k-1) + 2^{2} *(k-2) + ... + 2^{k-1} *1 \right)2S(k)=(21∗(k−1)+22∗(k−2)+...+2k−1∗1)
两者相减得：
S(k) = \left(-2^{0} *(k-1) + 2^{1} + 2^{2} + ... + 2^{k-2} + 2^{k-1} \right)S(k)=(−20∗(k−1)+21+22+...+2k−2+2k−1)
化简一下：
（不好意思我实在受不了这个编辑器了。。。
所以 heapify() 时间复杂度是 O(n).
以上就是堆的三大重要操作，最后一个 heapify() 虽然不能直接操作，但是堆排序中用到了这种思路，之前的「选择排序」那篇文章里也提到了一些，感兴趣的同学可以后台回复「选择排序」获得文章～至于堆排序的具体实现和应用，以及为什么实际生产中并不爱用它，我们之后再讲。
最后再说一点题外话，最近发现了几篇搬运我的文章到其他平台的现象。每篇文章都是我精心打造的，都是自己的心肝宝贝，看到别人直接搬运过去也没有标明作者和来源出处实在是太难受了。。为了最好的阅读体验，文中的图片我都没有加水印，但这也方便了他人搬运。今天考虑再三，还是不想违背自己的本意，毕竟我的读者更为重要。
所以如果之后有小伙伴看到了，恳请大家后台或者微信告诉我一下呀，非常感谢！
我在各大平台同名，请认准「码农田小齐」～
如果你喜欢我的文章或者有收获的话，麻烦给我点个「赞」或者「在看」给我个小鼓励呀，会让我开心好久～
想跟我一起玩转算法和面试的小伙伴，记得关注我，我是小齐，我们下期见。
