是否有 O（n） 算法来构建最大堆？

我不这么认为。我认为你能做的最好的事情是 O（log n） 或更好一点，比如 fib 堆。

如果您使用斐波那契堆，则会得到摊销的 O（1） 插入。因此，您可以从数组中构建一个摊销 O（n） 的最大堆。

这样的实施，我离开作为一个练习*。

_{*不过，维基百科页面上有链接的示例实现。}

是的，有：构建堆。

是的，就像以下代码一样：

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）。