Ace Test series: Algorithms - Sorting

Question

Comments

use the concept of min heap

---

If we construct min heap wouldn't it take O(n log n) time?

---

no...construction of heap(build heap)...is

O(n) then delete three element..

Answer 1

construction of build heap it will take  n comparisons{minheap}

after that you have to delete root element for minimum(you have to replace root will last element of tree it will take log(n) time to maintain heap property ).you have to delete three element it will take time more than 3*log(n).thats why it will take in ans O(LOG(N))

 so Total comparisons = N+O(log(n))

in question is not asking for time complexity( in this case ans will be C ).