Heap: kth largest element in a stream

Problem Statement:

You are given an infinite stream of integers, you need to find the kth largest element at any point of time.

Example

Input: Infinite stream of integers
k = 3

10,
20,
11,
70,
50,
40,
100,
5,
…

Output:

The k’th largest element is NA.
The k’th largest element is NA.
The k’th largest element is 10
The k’th largest element is 11
The k’th largest element is 20
The k’th largest element is 40
The k’th largest element is 50
The k’th largest element is 50

Solution

We will use minheap to solve this problem.

We will maintain min heap of K size.

Since we are using min-heap, the topmost element would be the smallest in the heap.

And our heap size is k, the top element would be the kth largest in the stream.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 

using namespace std;

class KthLargest {
public:
    priority_queue <int , vector <int> , greater <int> > pq;
    int K;
    KthLargest(int k, vector<int>& nums) {
        K = k;
        for(auto &x : nums) 
        {
            pq.push(x);
            if(pq.size() > k) 
            {
                pq.pop();
            }
        }
    }
    int add(int val) 
    {
        pq.push(val);
        if(pq.size() > K)
            pq.pop();
        return pq.top();
    }
};

int main() 
{
    vector <int> nums = {4 , 5 , 8 , 2};
    int k = 3;
    KthLargest stream(k , nums);
    cout << stream.add(3) << " ";
    cout << stream.add(5) << " ";
    cout << stream.add(10) << " ";
    cout << stream.add(9) << " ";
    cout << stream.add(4) << " ";
    cout << endl;
    return 0;
}

Output:

4 5 5 8 8