Related Tags

data structures
heap

# Find the kth smallest element from an array using a min-heap

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.

## Algorithm

The following steps are involved in finding the $k^{th}$ smallest element using a min-heap.

1. Create a min-heap using the given array.

2. Remove the element at the root of the heap $k-1$ times.

3. The element on the root of the heap is the $k^{th}$ smallest element.

The illustration below further explains this concept.â€‹

Consider the array above.
1 of 6

## Implementation

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

data structures
heap