Creation of max Heap from stream of integer

Question

Since i know that if there is n element given in array and i want to create a max heap it took o(n) because logic is we apply heapify from last parent to root.

But my question is suppose if there is stream of integer is coming and i want to insert element in heap then after inserting n element what will be my time complexity.I think it goes to o(nlogn).

Because for completing each level number of operation will be

(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))

When i did sum of it i got nlogn + constant.So please clarify me what is wrong with it ?

Answer 1

Your analysis is correct. In the worst case, inserting n elements sequentially into a heap will result in Θ(n log(n)) time.

When the heap has i elements, and the i + 1-th element is inserted, then at the worst case, it will need to be bubbled up all the way to the top, which is Θ(log(i)). Thus the complexity for the sequence of operations, at worst case, is

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

where the last part follows from Stirling's Approximation.