是否有O(n)算法来构建最大堆？

Question

给定一个数组,是否有O(n)算法来构建最大堆？

Answer 1

是的,就像在这段代码中一样:

for (int i = N/2; i >= 0; --i)
    push_heap(heap + i, N - i);

(push_heap是一个函数,它接受指向堆的指针和堆大小,并推送堆顶部,直到遵守堆条件或节点到达堆的底部).

要了解为什么这是O(N)看完整的二叉树:

• 1/2元素(最后一级,i> N/2)最多下推0步 - > N/2*0操作
• 1/4元素(最后1级,i> N/4)最多下推1步 - > N/4*1次操作

• 1/8元素(最后2级,i> N/8)最多下推2步 - > N/8*2操作......

    N/4 * 1 + N/8 * 2 + N/16 * 3 + ... =
  
    N/4 * 1 + N/8 * 1 + N/16 * 1 + ... +
              N/8 * 1 + N/16 * 2 + ... =
  
    N/4 * 1 + N/8 * 1 + N/16 * 1 + ... +    // < N/2
              N/8 * 1 + N/16 * 1 + ... +    // < N/4
                        N/16 * 1 + ... +    // < N/8
                                   ... =    // N/2 + N/4 + N/8 + ... < N
  

希望数学不是太复杂.如果你在树上查看并添加每个节点可以向下推的程度,你会看到上限O(N).

Answer 2

是的有:建立一个堆.

Answer 3

我不这么认为。我认为你能做的最好的事情是 O(log n) 或使用像 fib 堆这样的东西更好一点。