从整数流创建最大堆
因为我知道如果数组中有n个元素，并且我想创建一个最大堆，它将花费o（n），因为逻辑是我们将heapify从最后一个父项应用到根。
但我的问题是假设如果有整数流来了，我想插入堆中的元素，然后插入n元素之后什么是我的时间复杂性。我认为它去o（nlogn） 。
因为完成每个级别的操作将会有数量
（2 ^ L）* L其中L是将从零开始到（（logn）-1）的树的深度，
总和= 0 + 1 *（2 ^ 1）+ 2 *（2 ^ 2）........... +（LOGN-1）（2 ^（LOGN-1））
当我做了它的总和，我得到了nlogn + constant.So请澄清我有什么问题吗？
你的分析是正确的。 在最坏的情况下，将n个元素顺序插入一个堆将导致Θ（n log（n））时间。
当堆有i个元素时，插入第i + 1个元素，那么在最坏的情况下，它将需要一直冒泡到顶部，即Θ（log（i））。 因此，在最坏的情况下，操作顺序的复杂性是
（log（i））=Θ（log（i！））=Θ（n log（n）），
最后一部分来自斯特林的逼近。
链接地址: http://www.djcxy.com/p/39899.html