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-1 $$
那么总的替换次数 S(k) 就是两者相乘再相加：
$$S(k) = \left(2^{0} *(k-1) + 2^{1} *(k-2) + … + 2^{k-2} *1 \right)$$
这是一个等比等差数列，规范的求和形式就是 错位相减法。
那么
$$2S(k) = \left(2^{1} *(k-1) + 2^{2} *(k-2) + … + 2^{k-1} *1 \right)$$
两者相减得：
$$S(k) = \left(-2^{0} *(k-1) + 2^{1} + 2^{2} + … + 2^{k-2} + 2^{k-1} \right)$$
化简一下：
（不好意思我切实受不了这个编辑器了。。。
所以 heapify() 工夫复杂度是 O(n).
以上就是堆的三大重要操作，最初一个 heapify() 尽管不能间接操作，然而堆排序中用到了这种思路，之前的「抉择排序」那篇文章里也提到了一些，感兴趣的同学能够后盾回复「抉择排序」取得文章～至于堆排序的具体实现和利用，以及为什么理论生产中并不爱用它，咱们之后再讲。
如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！
我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！
更多干货文章见我的 Github: https://github.com/xiaoqi6666…