Heaps: Find kth smallest in an unsorted array

Problem Statement:

You are given an array and a number K, you need to find the kth smallest element.

Example

Input: arr[] = {5, 20, 10, 7, 1}, N = 5, K = 2
Output: 5

Solution

We will use max heap to solve this problem.

1. We create priority queue for first k elements.

2. Then we pop the element from the top of the priority queue after every insertion of the elements.

3. Once all the elements are inserted into the PQ, we print the top of the priority queue as the answer.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;

void get_k_th_smallest(vector<int>& v, int K)
{

    int N  = v.size();
    priority_queue<int> heap1;
 
    for (int i = 0; i < N; ++i) 
    {
 
        heap1.push(v[i]);

        if (heap1.size() > K) 
        {
            heap1.pop();
        }
    }
 
    cout << "The smallest element is " << heap1.top() << endl;
}
 
// Driver code
int main()
{
    // Given array
    vector<int> vec = { 5, 3, 4, 2, 1, 0 };
 
     int k = 2;
 
    get_k_th_smallest(vec, k);
 
    return 0;
}

Output:

The smallest element is 1