Find K’th largest element in a stream in Java

In this tutorial, we will find the K’th largest element in an input stream in Java. We will know what is an input stream and how we can find K’th largest element in an input stream after inserting data each time. Here we will use a min Heap of K size and retrieve the smallest of the heap, will be K’th largest for us then.

Java program to find K’th largest element in input stream using min heap:

An input stream is running the input of a sequence of data. For example, if we are to find the 4th largest element in a stream, say 20, 10, 80, 75 then we will feed this into min-heap of size 4 and it will give us 10, which is actually 4th largest. Now, we will understand the concept through 2 cases:

Case 1: new input is greater than the root of the min-heap.

suppose, we add 16 to the stream, which is greater than 10, so it will replace the root of min-heap with 10, and min heap will give us 16. 16 will be our new 4th largest element.

Case 2: new input is less than the root of the min-heap.

suppose, we add 7 to the stream, which will not affect our 4th largest element that was 10, so it will make no change to the min-heap.

 

One simple approach can be is to maintain a sorted array of size K and finding the largest element of it on O(1) time. When there is a new input in the stream it will take O(k) time to sort the array. So, the total time complexity will be O(k).

This approach uses min-heap and heapify function to implement the solution to the problem.  Here, time complexity to return the root of min-heap will be O(1) and heapify function will take O(log K) time, so this can be an efficient approach.

The code is divided into 3 parts:

  1. The main function which takes the value of K and calls KLargest function where actual implementation starts.
  2. The MinHeap class for implementing min-heap and having memeber functions that will be used in our KLargest function like buildHeap(), replaceMin(), getMin(), and minHeapify().
  3. The KLargest function which creates an instance of MinHeap and takes the running input every time and prints the K’th Largest after every input.

Now Let’s understand it by the code:

 

import java.util.Scanner;
public class KthLargestinStream{
    static Scanner sc = new Scanner(System.in);
    
    
    // Part 1 of the code
    public static class MinHeap{
        int[] heapArray;
        int capacity;
        int heapSize; // current size of heap.
        
        MinHeap(int[] a, int size){
            heapSize = size;
            heapArray = a;
        }
        
        public int getMin(){
            return heapArray[0];
        }
        
        
        public void minHeapify(int i){
            int left = 2*i + 1;
            int right =  2*i + 2;
            int smallest = i;
            if(left < heapSize && heapArray[left]<heapArray[i])
            smallest = left;
            if(right < heapSize && heapArray[right]<heapArray[smallest])
            smallest = right;
            if(smallest!=i){
                int temp = heapArray[i];
                heapArray[i] = heapArray[smallest];
                heapArray[smallest]= temp;
                minHeapify(smallest);
            }
            
        }
        
        public void replaceMin(int x){
            heapArray[0] = x;
            minHeapify(0);
        }
        
        public void buildHeap(){
            int i = (heapSize - 1)/2;
            while(i>=0){
                minHeapify(i);
                i--;
            }
        }
        
    }
    
    static MinHeap minHeap;
    
    
    // Part 2 of the code
    public static void kLargest(int k){
        int countofElements = 0;
        int newElement;
        // Create min heap of size k
        int[] array = new int[k];
        minHeap = new MinHeap(array,k); //object of class MinHeap
        
        while(true){
            //Take next element
          System.out.println("Enter next element.");    
          newElement = sc.nextInt();
          System.out.println(newElement);
          
          if(countofElements < k-1){
              array[countofElements]=newElement;
              countofElements++;
          }else{
              if(countofElements == k-1){ //kth element entered.
                  array[countofElements] = newElement;
                  minHeap.buildHeap();
              }else{ // if next element is greater than kth element, replace the root. 
                  if(newElement > minHeap.getMin()){
                      minHeap.replaceMin(newElement);
                  }
              }
              
              System.out.println(k + " largest element is " + minHeap.getMin());
              countofElements++;
              
          }
        }
    }
    
    
    //Part 3 of the code
    public static void main(String[] args){
        int k = 3;
        System.out.println("K is " + k);
        kLargest(k);
        
    }
}

Output:

K is 3
Enter next element.
20
Enter next element.
10
Enter next element.
70
3 largest element is 10
Enter next element.
42
3 largest element is 20
Enter next element.
8
3 largest element is 20
Enter next element.
56
3 largest element is 42
Enter next element.
26
3 largest element is 42
Enter next element.
90
3 largest element is 56
Enter next element.

I hope this tutorial helps you understand this concept better with the help of the code given above.
For similar Java programs, you can also see: Kth Largest element in an array using QuickSort in JAVA

Thank You.

Leave a Reply

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