如何O(n)实现heapify呢?

比如，给你一堆integer，比如100个，
怎么用O(n)实现heap呢?

hepify 初始话复杂度就是O（n）。
"假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。经评论提醒，H=log2(N)  +  1”


链接：https://www.zhihu.com/question/20729324/answer/231955716

网上能搜到的heapify代码或者伪代码基本上都是O(n)的。 一般面试里面问得比较多的是为什么heapify是O(n)

可以参考这个写的很清楚. 就不多叙述了.感谢
https://stackoverflow.com/questi ... -on-time-complexity

richarduu 发表于 2020-9-23 05:42
网上能搜到的heapify代码或者伪代码基本上都是O(n)的。 一般面试里面问得比较多的是为什么heapify是O(n)

为什么呢？