是否有一个O（n）的算法来构建一个最大堆？ [英] Is there a O(n) algorithm to build a max-heap?

问题描述

由于数量的排列，有一个O（n）的算法来构建一个最大堆？

Given a array of number, is there a O(n) algorithm to build a max-heap?

推荐答案

是的，像这样code：

Yes, like in this code:

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

（ push_heap 是接受一个指向堆的堆大小和推堆的顶部，直到堆条件得到尊重或节点到达功能堆的底部）。

(push_heap is a function that accepts a pointer to a heap and the heap size and pushes the top of the heap until the heap conditions are respected or the node reaches the bottom of the heap).

要知道为什么，这是O（N）看完全二叉树：

To get why this is O(N) look at the complete binary tree:

• 在1/2元素（最后一个层次，我> 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操作 ......

• 1/2 elements (last level, i > N/2) are pushed down at most 0 steps -> N/2 * 0 operations
• 1/4 elements (last-1 level, i > N/4) are pushed down at most 1 step -> N/4 * 1 operations

• 1/8 elements (last-2 level, i > N/8) are pushed down at most 2 steps -> N/8 * 2 operations ...

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

Hope that math is not really too complicated. If you look on the tree and add how much each node can be pushed down you'll see the upper bound O(N).

这篇关于是否有一个O（n）的算法来构建一个最大堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！