Finding the $k^{th}$ smallest element of an array efficiently may seem a little tricky at first. However, it can be found easily using a min-heap or by sorting the array.
The following steps are involved in finding the $k^{th}$ smallest element using a min-heap.
Create a min-heap using the given array.
Remove the element at the root of the heap $k-1$ times.
The element on the root of the heap is the $k^{th}$ smallest element.
The illustration below further explains this concept.â€‹
The following code snippet implements the above algorithm in C++.
#include <bits/stdc++.h> using namespace std; int main () { // Creating a min-heap. priority_queue <int, vector<int>, greater<int> > minheap; minheap.push(10); minheap.push(1); minheap.push(0); minheap.push(8); minheap.push(7); minheap.push(2); // Removing the element at the root of the min-heap k-1 times. for(int i = 0; i < 2; i++){ minheap.pop(); } // Displaying the element at the root of the min-heap. cout<<"The third smallest element in the given array is: " <<minheap.top() << endl; return 0; }
RELATED TAGS
View all Courses