Initializing the min-heap with all numbers will take O(N)

Hey guys,

I am wondering why the time complexity of initializing heap with all numbers is O(N), thanks for your help !!!


Type your question above this line.


Hello! you can find here the answer you are looking for Time Complexity of building a heap - GeeksforGeeks

1 Like

Hi @Nicole,

Firstly we use a max heap and not a min heap.

The reason the time complexity is O(N) is because we put in the max heap k elements in order to find the K smallest number so in the case where K == N we would put all N number is the max heap thus having a time complexity of O(N).

Hope this helps.