algorithm - 从整数流创建最大堆

Question

因为我知道如果数组中有 n 个元素并且我想创建一个最大堆它需要 o(n) 因为逻辑是我们从最后一个父级应用 heapify 到根。

但我的问题是假设是否有整数流即将到来并且我想在堆中插入元素然后在插入 n 元素之后我的时间复杂度是多少。我认为它会转到 o(nlogn) .

因为完成每个级别的操作数将是

(2^L)*L where L will be depth of tree which will start from zero to ((logn)-1)

Sum=0+1*(2^1)+2*(2^2)...........+(logn-1)(2^(logn-1))

当我对它求和时，我得到了 nlogn + 常量。所以请解释一下它有什么问题？

Answer 1

您的分析是正确的。在最坏的情况下，将 n 个元素按顺序插入堆中将导致 Θ(n log(n)) 时间。

当堆有i个元素，第i + 1个元素被插入，那么在最坏的情况下，它需要冒泡所有到顶部的方式，即 Θ(log(i))。因此，在最坏的情况下，操作序列的复杂度是

∑_{i = 1, ..., n}Θ(log(i)) = Θ(log(i!))= Θ(n log(n)) em>,

最后一部分来自 Stirling's Approximation .