1

我试图理解一个关于堆的简单概念。

我知道使用Floyd算法的BuildHeap需要 Theta(n) 来构建大小为 n 的堆。我们获得这个运行时间的方法是自下而上构建堆——这样，更大数量的堆做的工作更少。

我对这个概念进行了练习，但有一个不同的细节，问题如下：

“假设已知的 'FixHeap' 采用 Theta(log(log(n)) 而不是 Theta(log(n))。BuildHeap 算法使用新的 'FixHeap 构建大小为 N 的最大堆的运行时间是多少？ ' 算法（现在只需要 Theta(log(log(n)))"

我不明白新给定的 FixHeap 的运行时间如何影响整体算法运行时间。你能帮我理解这些变化会是什么吗？

FixHeap 是已知的算法，它将父节点与其左右子节点进行比较，并将最大值放在父节点中。作为叶子的父节点的顶点上的 FixHeap 最多会进行一次替换，而该顶点的父节点可能会进行两次替换，依此类推。

编辑：当前 BuildHeap 运行时间由以下表达式计算：

(n/4) * 1 + (n/2) * 2 + (n/3) * 3 +......+ 1 * logn-1

仅仅因为有 n/4 个叶子的父节点最多进行 1 次更改，并且有 n/2 个叶子最多进行 2 次更改，依此类推......

我现在看不到公式的变化。

谢谢！

4

1 回答 1

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) 时间，从而为我们提供所需的下限。

希望这可以帮助！

于 2013-02-08T17:20:27.900 回答