Find K’th largest element in a stream in C++

In this tutorial, we are going to learn how to find the K-th largest element in a stream of numbers using C++.

Naive Solution for finding K-th largest element in a stream

We can create an array of size K to store the K largest elements. The elements in the array must be in sorted order. So at any point in time, the element which is at the index 0 would be the K-th largest element. If we receive a new element in the stream which is greater than the current K-th largest element then the K-th largest element will be removed from the array, and the new element will be placed in a proper position such that the array remains sorted.

The time complexity of deleting the element at index 0 and inserting a new element is O(k).
The time complexity of finding out the K-th largest element is O(1).

#include<bits/stdc++.h>
using namespace std;
void insertionSort(int a[],int i){
    int key = a[i];
    int j = i-1;
    while(j >= 0 && a[j] > key){
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = key;
}
void replaceAndSort(int a[],int k,int key){
    int i = 1;
    while(i < k && a[i] < key){
        a[i-1] = a[i];
        i++;
    }
    a[i-1] = key;
}
int main(){
    int k,x;
    string s;
    cout<<"Enter the value of K"<<endl;
    cin>>k;
    int arr[k];
    for(int i = 0;i < k;i++){
        cout<<"Enter a new value into the stream"<<endl;
        cin>>arr[i];
        insertionSort(arr,i);
    }
    cout<<"The K-th greatest element is "<<arr[0]<<endl;
    while(true){
        cout<<"Enter a new value into the stream"<<endl;
        cin>>s;
        if(s == "quit"){
            //End of the stream
            break;
        }
        else{
            x = stoi(s);
            if(x > arr[0]){
                replaceAndSort(arr,k,x);
            }
            cout<<"The K-th greatest element is "<<arr[0]<<endl;
        }
    }
}

In the insertionSort() function, we are using the standard insertion sort principle for sorting the first K elements. Our job is to insert a new element in a sorted array. We should find a position such that the elements that are on the left side of it are less than or equal to the new element and the elements that are on the right side are greater than are equal to the new element. After finding such a position the new element must be inserted into it.

The replaceandSort() function should be called when we find an element in the stream which is greater than the current K-th largest element. This function does a similar job like the insertionSort() function. But instead of traversing the array starting from the back, the array will be traversed starting from the front and the new element is inserted in a proper position after removing the current K-th largest element.

At any point in time, the element which is at the index 0 would be the K-th largest element.

Optimal Solution for finding the K-th largest element in a stream

We can create a Min Heap to store the K largest elements. So the element which is at the root will be the K-th largest element. If we receive a new element from the stream which is greater than the K-th largest element then the root will be replaced with the new element and heapify is called on the root to restore the Min Heap property.

The time complexity of deleting the element at the root and inserting a new element is O(logk).
The time complexity of finding out the K-th largest element is O(1).

 

#include<bits/stdc++.h>
using namespace std;
void swap(int heap[],int i,int j){
    //Swapping two elements in heap
    int x = heap[i];
    heap[i]= heap[j];
    heap[j] = x;
}
void heapifyOnInsertion(int heap[],int k,int i){
    //Heapify on insertion of first K elements in the stream
    int p = (i-1)/2;
    if(heap[p] > heap[i]){
        swap(heap,p,i);
        heapifyOnInsertion(heap,k,p);
    }
}
void heapify(int heap[],int k,int i){
    int l = 2*i + 1;
    int r = 2*i + 2;
    int mini = heap[i];
    if(l < k && heap[l] < mini){
        mini = heap[l];
    }
    if(r < k && heap[r] < mini){
        mini = heap[r];
    }

    if(mini != heap[i]){
        if(mini == heap[l]){
            swap(heap,i,l);
            heapify(heap,k,l);
        }
        else{
            swap(heap,i,r);
            heapify(heap,k,r);
        }
    }
}
int main(){
    int k,x;
    string s;
    cout<<"Enter the value of K"<<endl;
    cin>>k;
    int heap[k];
    for(int i = 0;i < k;i++){
        cout<<"Enter the next value in stream"<<endl;
        cin>>x;
        heap[i] = x;
        heapifyOnInsertion(heap,k,i);
    }
    cout<<"The K-th greatest element is "<<heap[0]<<endl;
    while(true){
        cout<<"Enter the next value in stream"<<endl;
        cin>>s;
        if(s == "quit"){
            //End of the stream
            break;
        }
        else{
            x = stoi(s);
            if(x > heap[0]){
                heap[0] = x;
                heapify(heap,k,0);
            }
            cout<<"The K-th greatest element is "<<heap[0]<<endl;
        }
    }
}

Output:

Enter the value of K
5
Enter a new value into the stream
6
Enter a new value into the stream
3
Enter a new value into the stream
5
Enter a new value into the stream
2
Enter a new value into the stream
7
The K-th greatest element is 2
Enter a new value into the stream
1
The K-th greatest element is 2
Enter a new value into the stream
5
The K-th greatest element is 3
Enter a new value into the stream
8
The K-th greatest element is 5
Enter a new value into the stream
4
The K-th greatest element is 5
Enter a new value into the stream
quit

We are using the heapifyOnInsertion() function to insert the first K elements into the Min Heap and to maintain the Min Heap property. The heapifyOnInsertion() function compares the newly inserted element with its parent. If its value is less than its parent value then they will be swapped. If the elements are swapped, a recursive function call is made on the new parent.

After inserting the K elements, if we find a new element in the stream which is greater than the current K-th largest element the root must be replaced with the new element. The heapify() function is called on the root to maintain the Min Heap property.

The heapify() function compares the value of the root with the child having the least value among the two children. If the value of the root is greater than the child’s value, the root and the child will be swapped. If a swap takes place then a recursive function call is made on the child.

At any point in time, the element which is at root is the K-th largest element.

 

We hope that you have got a clear idea of how to find the K-th largest element in a stream of numbers using C++.