a shot of dev knowledge

RELATED TAGS

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

Finding the kthk^{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 kthk^{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 k1k-1 times.

  3. The element on the root of the heap is the kthk^{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

RELATED COURSES

View all Courses

Keep Exploring