educative.io

Does not look optimal: Kth smallest using min Heap

Courses
,
#1

In the Alternate Approach Section to find the Kth smallest number using minHeap, you have suggested to use an heap size of N to insert all elements. Can’t this be done in a heap size of (N-k+1) just as we did for maxHeap ? We can compare all remaining elements with top of the heap(which is the minimum) and remove the top if the current element is greater. We will finally have (k-1) minimum elements outside the heap. and n-k+1 maximum elements inside the heap. The root/top of the heap will represent the kth smallest element.

Hence time complexity for this approach should be O(k*log(N-k)+(N-k))
and space complexity should be O(N-k)

#2

Hi @Rupali_Patro

My name is Shahrukh Naeem. I hope everything is going well with you. Thank you for reaching out about this. I will try my best to answer your query!

Min-Heap can be used to find the kth smallest element, by inserting all the elements into Min-Heap and then and call extractMin() function K times.We will follow the following steps to solve the problem:

  • Insert all the array elements into the Min-Heap
  • Call extractMin() function K times
  • Return the value obtained at the last call of extractMin() function

Time complexity: O(N + K Log N).

Auxiliary Space: O(N)

I hope that this guide is helpful. Remember that I am always available via message to help you with any difficulty you might encounter.

Regards,

Happy Learning :slight_smile: