我试图理解有关堆的一个简单概念。
我知道 BuildHeap 使用 Floyd 算法需要 Theta(n) 来构建大小为 n 的堆.我们获得此运行时间的方法是自下而上构建堆 - 这样，堆的数量越大，工作越少。
我对这个概念进行了练习，但有一个不同的细节，问题如下:
"Suppose the known 'FixHeap' takes Theta(log(log(n)) instead of Theta(log(n)). What will be the running time of the BuildHeap algorithm to build a max heap of size N using the new 'FixHeap' algorithm(the one which takes now only Theta(log(log(n)))"
我不明白新给定的 FixHeap 的运行时间如何影响整个算法的运行时间。你能帮我了解一下会有哪些变化吗？
FixHeap 是已知的算法，它将父节点与其左右子节点进行比较，并将最大值放在父节点中。 FixHeap 在作为叶子父节点的顶点上最多进行一次替换，而该顶点的父节点可能进行两次替换，依此类推。
EDIT :当前 BuildHeap 运行时间由以下表达式计算:
(n/4) * 1 + (n/2) * 2 + (n/3) * 3 +......+ 1 * logn-1
仅仅因为有 n/4 个叶子的父代最多做 1 次变化，还有 n/2 个最多做 2 次变化等等...
我现在只是看不到公式的变化。
谢谢!
最佳答案
这个算法仍然需要 Θ(n) 的时间。看到这一点，我们可以证明该算法是 O(n) 和 Ω(n)。
对于 O(n) 部分，请注意此算法显然不会比 FixHeap 每次花费 O(log n) 时间的版本慢。由于 heapify 算法在第二种情况下需要 O(n) 时间，因此我们也可以获得 O(log log n) 时间情况下的 O(n) 时间限制。
对于 Ω(n) 部分，请注意 heapify 算法通过对数组前半部分中的每个元素执行一次 FixHeap 过程来工作。迭代 n 元素数组的一半至少需要 Ω(n) 的时间，从而为我们提供所需的下限。
希望这对您有所帮助!
关于algorithm - BuildHeap - Floyd 算法 - FixHeap 概念，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14777642/