Programa Java para encontrar el elemento K’th más grande en una secuencia

Dada una secuencia infinita de números enteros, encuentre el k-ésimo elemento más grande en cualquier punto del tiempo.
Ejemplo: 

Input:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}
k = 3

Output:    {_,   _, 10, 11, 20, 40, 50,  50, ...}

El espacio extra permitido es O(k). 

Hemos discutido diferentes enfoques para encontrar el k-ésimo elemento más grande en una array en las siguientes publicaciones. 
K’th elemento más pequeño/más grande en array no ordenada | Establecer 1  
k’ésimo elemento más pequeño/más grande en array sin clasificar | Conjunto 2 (Tiempo lineal esperado)
K’th Elemento más pequeño/más grande en array no ordenada | Conjunto 3 (Tiempo lineal en el peor de los casos)
Aquí tenemos una secuencia en lugar de una array completa y podemos almacenar solo k elementos.

Una solución simple es mantener una array de tamaño k. La idea es mantener la array ordenada de modo que el k-ésimo elemento más grande se pueda encontrar en el tiempo O(1) (solo necesitamos devolver el primer elemento de la array si la array está ordenada en orden creciente) 
Cómo procesar un nuevo elemento de ¿corriente? 
Para cada nuevo elemento en el flujo, verifique si el nuevo elemento es más pequeño que el k-ésimo elemento más grande actual. Si es así, ignóralo. Si no, elimine el elemento más pequeño de la array e inserte un nuevo elemento en orden. La complejidad temporal del procesamiento de un nuevo elemento es O(k).

Una mejor solución es utilizar un árbol de búsqueda binario autoequilibrado de tamaño k. El k’ésimo elemento más grande se puede encontrar en el tiempo O(Logk). 
¿Cómo procesar un nuevo elemento de flujo? 
Para cada nuevo elemento en el flujo, verifique si el nuevo elemento es más pequeño que el k-ésimo elemento más grande actual. Si es así, entonces ignóralo. Si no, elimine el elemento más pequeño del árbol e inserte un nuevo elemento. La complejidad temporal del procesamiento de un nuevo elemento es O(Logk).

Una solución eficiente es usar Min Heap de tamaño k para almacenar k elementos más grandes de flujo. El k-ésimo elemento más grande siempre está en la raíz y se puede encontrar en el tiempo O(1). 
¿Cómo procesar un nuevo elemento de flujo? 
Compare el nuevo elemento con la raíz del montón. Si el nuevo elemento es más pequeño, ignórelo. De lo contrario, reemplace la raíz con el nuevo elemento y llame a heapify para la raíz del montón modificado. La complejidad temporal de encontrar el k’ésimo elemento más grande es O(Logk).
 

// Java program for the above approach
import java.io.*;
import java.util.*;
  
class GFG {
    
  /*
  using min heap DS
  
  how data are stored in min Heap DS
         1
       2   3
  if k==3 , then top element of heap
  itself the kth largest largest element
  
  */
  static PriorityQueue<Integer> min;
  static int k;
  
  static List<Integer> getAllKthNumber(int arr[])
  {
      
    // list to store kth largest number
    List<Integer> list = new ArrayList<>();
  
    // one by one adding values to the min heap
    for (int val : arr) {
  
      // if the heap size is less than k , we add to
      // the heap
      if (min.size() < k)
        min.add(val);
  
      /*
      otherwise ,
      first we  compare the current value with the
      min heap TOP value
  
      if TOP val > current element , no need to
      remove TOP , bocause it will be the largest kth
      element anyhow
  
      else  we need to update the kth largest element
      by removing the top lowest element
      */
  
      else {
        if (val > min.peek()) {
          min.poll();
          min.add(val);
        }
      }
  
      // if heap size >=k we add 
      // kth largest element
      // otherwise -1
  
      if (min.size() >= k)
        list.add(min.peek());
      else
        list.add(-1);
    }
    return list;
  }
  
  // Driver Code
  public static void main(String[] args)
  {
    min = new PriorityQueue<>();
  
    k = 4;
  
    int arr[] = { 1, 2, 3, 4, 5, 6 };
  
    List<Integer> res = getAllKthNumber(arr);
  
    for (int x : res)
      System.out.print(x + " ");
  }
  
    // This code is Contributed by Pradeep Mondal P
}

Producción:

K is 3
Enter next element of stream 23
Enter next element of stream 10
Enter next element of stream 15
K'th largest element is 10
Enter next element of stream 70
K'th largest element is 15
Enter next element of stream 5
K'th largest element is 15
Enter next element of stream 80
K'th largest element is 23
Enter next element of stream 100
K'th largest element is 70
Enter next element of stream
CTRL + C pressed

¡ Consulte el artículo completo sobre el K’ésimo elemento más grande en una secuencia para obtener más detalles!