In this problem, it says “Given ‘N’ ropes, we need O(N*logN) to insert all the ropes in the heap”, however, in previous problems, it says, to build a heap, it just uses O(N) time. Which one we should mention if we are asked in the interview and how we gonna explain. Thank you all.

Hi @Jason1,

Sorry for the confusion. Building (or initializing) a heap with ‘N’ elements will take O(N) whereas if we insert elements one by one in the heap it will take O(N*logN).

To understand why build a heap will take O(N), please see: https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

Hope this clarifies your question.

Hi, thank you for your reply. Can I understand that if we use heapq.heapify(array) to heapify an existing array with N elements, the time complexity is asymptotically equal to O(N) based on some complicated math. And if we use

heap = []

for num in array:

heapq.heappush(heap, num)

to build the heap one element by one, which is using O(N*logN) time complexity.

Sorry, I think the time complexity is O(n+n*log(n)), because initialing with array takes O(n), inserting node during while takes o( n*log(n)), is that right? @Design_Gurus

Initializing the heap by adding elements one by one takes O(N*logN). Then the ‘while’ loop takes O(N*logN); hence total complexity will be:

O(N*logN + N*logN) => O(2*N*logN) => O(N*logN)

On a side note, O(N + N*logN) is asymptotically equivalent to O(N*logN) as “N < N*logN”.