algorithm - 是否有 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 个元素(last-1 层，i > N/4)最多被下推 1 步 -> N/4 * 1 次操作

• 1/8 个元素(last-2 level，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)。