Heap: Return k largest element

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

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *