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 (A) theta(logn) (B) theta(n) (C) theta(nlogn) (D) theta(n^2)
(A)
A
(B)
B
(C)
C
(D)
D
Answer: (B)
Explanation:
We can reduce the problem to build heap for 2n elements. Time taken for build heap is O(n).
Hence (B) is the correct answer.
Quiz of this Question
Please comment below if you find anything wrong in the above post
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!