Given an unsorted array “arr”, find and print the “kth” smallest/largest element of the array.
- The method of sorting the array.
- The method of using a min-heap data structure.
- The method of using a max-heap data structure.
By sorting the array
We can sort the given array “arr”, and then access the element with index k. After sorting, for any valid index of arr “i”, the ith smallest element gets stored at the index i.
Heap is also called a priority queue. It’s a data structure that stores elements in a sorted fashion. It provides access to only the top element in it viz the element with the highest priority. The order of the elements in a heap is determined by tier priority. But what is a priority?
It could be any parameter for the comparison of two data items of the same type. For example, the priority of two elements could be determined by checking which of them is larger, a string may have a higher priority over another if it is lexicographically smaller than the other, etc.
In this method, we shall use a min-heap. It always stores the elements in an order such that the smallest element is always available at the top. We push all the elements from the array in the min-heap. Then we remove the top element from the heap repeatedly k-1 times. Therefore the kth element that is present at the top of the heap is also the kth smallest element.
The concept here is similar to that in the above. The difference here is that instead of a min-heap, we use a max-heap. We iterate over the elements of the array, for each of which:
* We push it into the heap.
* If the size of the heap exceeds k, we pop off the top element of the heap.
At the end of this process, the smallest k elements of the given array will be present in the heap. The top of the heap is the kth smallest element as required, which we shall return.