【LintCode, heap】为什么Heapify这题的时间复杂度是O(n)？

题目要求和解题代码请见附件贴图。
我想请问一下大家，程序的主函数是一个for循环，调用到的siftdown函数里面是一个while循环。
为什么还可以在O(n)的时间复杂度里完成呢？

楼主看这里：https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap

中心思想是：首先把head想做树，如果从下往上数（倒数）第h层的所有点已经是heapified的了，那么让倒数第h+1层的一个点heapify所需要的操作数最多是h步（最坏情况，最小堆里这个数是最大的，所以需要把它一层一层往下转移直到最底层）。所以对每一个h+1层的点（node）来说，复杂度O(h)。h+1层有这么多点：n/2^(k+1)，所以总得复杂度就是O(h) * (n/2^(k+1)) 再对所有层数求和。最终结果就是个O(n)的。
具体公式请到wikipedia查看，注意这句：This uses the fact that the given infinite series h / 2h converges to 2.

何打发123 发表于 2016-7-9 10:14
你好~ 想请问一下~ 如果按照这个道理 为什么siftup就是nlogn 呢？ 我觉得道理是一样的啊。。 想不明白 T T

这个siftup其实是那个straight forward的算法
每拿出来一个数放进数组（可以想象成queue）的最后，然后和他的father比较大小。
对于每个数是log(n)的时间（worst case）总共有n个数

道理确实是一样的，intuitively，不同的地方在于：假设h代表第几层，你的方法随着h增加，每层的点数也在增加，h最大的时候，也就是switch有可能最多的时候，点数是一层是2^h个点。但是lz得方法随着h的增加（倒数），每层的点数在减小，h最大的时候只有一个点。

你好~ 想请问一下~ 如果按照这个道理 为什么siftup就是nlogn 呢？ 我觉得道理是一样的啊。。 想不明白 T T

ericliu03 发表于 2016-7-14 06:00
这个siftup其实是那个straight forward的算法
每拿出来一个数放进数组（可以想象成queue）的最后，然后 ...

soga!  谢谢你的解释！虽然我没法严格的推导出来 但是有了个一个大概的意思了  感谢你啊！