Heap quiz question

#1

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is. Please explain the solution

#2

Time complexity for rearrangement in a binary heap due to heapify function is O(logn).
And since we have to insert n elements, the overall time complexity will be of the order O(nlogn).

#3

sir but correct answer given in the quiz is O(N)

#4

Oh yes sorry. The time complexity of building an array from a heap is O(nlogn). But the time complexity of building a heap from an array is O(n). There is some mathematics involved in the proof.


Check this and tell me if you get the logic.

#5

@sandeep021 Please mark your doubt as resolved if you are satisfied.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.