Algorithm which uses Max heap to find i smallest elements

Question

Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinct

Please use max heap to explain the working

input : n distinct elements

output : i smallest elements

Answer 1

Using max heap we can find i smallest elements in O( n * log i ) time

this method is very popular in coding interviews

Comments

@[ Jiren ] Nice answer 

thank you ;)

---

We have taken 'i'  to be constant right?  That's why we r going from O((n-i) logi + i)  to O(n(logi)).. Right?

---

@KartikGawande 

NO

Even if i depends on “n” like i = n

the time complexity still wont exceed n*logi because (n-n)*logi+n = n which is O(nlogn) 

Also remember that we cant take any parameter as constant unless mentioned in Algorithms and Data Structures

But writing Θ( n*logi ) is wrong we should write Θ( (n-i) logi + i )

---

@[ Jiren ] i see