NIELIT 2016 MAR Scientist C - Section C: 49

Question

We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is

• A. $\Theta (\log n)$
• B. $\Theta (n)$
• C. $\Theta (n \log n)$
• D. $\Theta (n^{2})$

Comments

B is the correct option.

Answer 1

Option B

we can use build heap method which will take O(n) time complexity

https://gateoverflow.in/459/gate2008-47