2. K smallest elements #

Created Sunday 16 February 2020

• We need a max heap for this. i.e we will swap all the largest elements. So the remaining ones will be the smallest.

Naive approach: sort() the array and return the first k T.C = O(nlogn) S.C = O(n)

The best approach: Using priority queue:

1. heapify the first k elements
2. Traverse the remaining elements, push if the array element is less than the largest in the priority queue. i.e all largest ones are removed eventually.
3. We have the minium in the priority queue.
4. Print in reverse order.

T.C = (heapify of k) + push( the remaining, if they are less tahn the max, our heap always have k elements, so log k) = klogk + (n-k)*logk = nlogk.