Problem Statement:
You are given an unsorted array of integer elements and “k”. You need to get the “k” largest elements.
Example
Input:
arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 20, 15, 10.
Solution
We can solve this problem by using sorting and get the result. But the time complexity wll be “nlogn”.
If we use min_heap it will be reduced to “nlogk”.
We will start inserting elements into min_heap.
And when the heap reaches “k”, then we pop the smallest elements.
At the end remaining elements in the heap are k largest elements.
Solution in C++
#include <algorithm>
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <list>
using namespace std;
void kth_largest_elements(vector<int>& v,int k)
{
//min_heap
priority_queue<int, vector<int>, greater<>> min_heap;
int n = v.size();
for (int i = 0; i < n; ++i)
{
//keep inserting elements into the heap
min_heap.push(v[i]);
// if the size exceeds K,
// then start popping the elements
if (min_heap.size() > k)
{
min_heap.pop();
}
}
//print the top of the heap to get the result.
cout << "The result is ";
while(min_heap.size() > 0)
{
cout<<min_heap.top()<<" ";
min_heap.pop();
}
}
int main()
{
vector<int> vec = { 7, 10, 4, 3, 20, 15};
int k = 3;
kth_largest_elements(vec, k);
return 0;
}
Output:
The result is 10 15 20