Promedio de números máximos de K en una secuencia

Dada una lista de números ‘N’ y un número entero ‘K’. La tarea es imprimir el promedio de los números máximos de ‘K’ después de cada consulta donde una consulta consiste en un elemento entero que debe agregarse a la lista de elementos. Nota: Las consultas se definen con una array de enteros ‘q’ Ejemplos:

Entrada: N = 4, K = 3, arr = {1, 2, 3, 4}, q = {7, 2, 1, 5} Salida: 4,666666 4,666666 4,666666 5,333333 Después de la consulta 1, arr = {1, 2, 3, 4, 7} y el promedio de K máximos (es decir, {3, 4, 7}) elementos es 4,666666. Después de la consulta 2, arr = {1, 2, 3, 4, 7, 2} y el promedio es 4,666666 para {3, 4, 7}. Después de la consulta 3, arr = {1, 2, 3, 4, 7, 2, 1} y el promedio es 4,666666 para {3, 4, 7}. Después de la consulta 4, arr = {1, 2, 3, 4, 7, 2, 5} y el promedio es 5,333333 para {4, 5, 7}. Entrada: N = 5, K = 4, arr = {1, 2, 2, 3, 3}, q = {2, 5, 1} Salida: 2,5 3,25 3,25

Enfoque: la estructura de datos Heap (Min Heap) se puede utilizar para resolver problemas como estos en los que la inserción y eliminación de los elementos se pueden realizar en tiempo O (log n).

• Inicialmente, almacene los k elementos máximos de la lista dada de elementos en el montón mínimo.
• Si el elemento entrante es menor o igual que el elemento actualmente en la raíz del montón mínimo, descarte el elemento ya que no tendrá ningún efecto en el promedio.
• De lo contrario, si el número es mayor que el elemento raíz, elimine la raíz del montón mínimo seguido de una inserción del nuevo elemento y luego calcule el promedio de los elementos actualmente en el montón.
• Imprima el promedio y repita los dos pasos anteriores para todos los elementos entrantes.

A continuación se muestra la implementación del enfoque anterior: 

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    // Function that returns the
    // average of max k elements in
    // the list after each query
    static void max_average_k_numbers(int n,
                                      int k,
                                      int m,
                                      int[] arr,
                                      int[] query)
    {
        double max_avg = 0.0;
 
        // min-heap to maintain
        // the max k elements at
        // any point of time;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
 
        // Sort the array
        // in ascending order
        Arrays.sort(arr);
 
        // add max k elements
        // to the heap
        double sum = 0;
        for (int i = n - 1; i >= n - k; i--) {
            pq.add(arr[i]);
            sum = sum + arr[i];
        }
 
        // perform offline queries
        for (int i = 0; i < m; i++) {
 
            // if the minimum element in
            // the heap is less than
            // the incoming element
            if (query[i] > pq.peek()) {
                int polled = pq.poll();
                pq.add(query[i]);
 
                // decrement the current
                // sum by the polled element
                sum = sum - polled;
 
                // increment sum by the
                // incoming element
                sum = sum + query[i];
            }
 
            // compute the average
            max_avg = sum / (double)k;
            System.out.println(max_avg);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 4;
        int k = 3;
        int m = 4;
        int[] arr = new int[] { 1, 2, 3, 4 };
        int[] query = new int[] { 7, 2, 1, 5 };
 
        max_average_k_numbers(n, k, m, arr, query);
    }
}

# implementation of the approach
# importing heapq module
import heapq
 
# Function that returns the
# average of max k elements in
# the list after each query
def max_average_k_numbers(n, k, m, arr, query):
    max_avg = 0.0
     
    # min-heap to maintain
    # the max k elements at
    # any point of time
    pq = []
    Sum = 0
     
    # Sort the array in ascending order
    arr.sort()
     
    # add max k elements to heap pq
    for i in range(n - 1, n - k - 1, -1):
        pq.append(arr[i])
        Sum += arr[i]
         
    # heapify the heap pq for maintaining the
    # heap property
    heapq.heapify(pq)
     
    # perform offline queries
    for i in range(m):
       
        # if the minimum element in
        # the heap is less than
         # the incoming element
        if query[i] > pq[0]:
            polled = pq[0]
            pq[0] = pq[-1]
            pq.pop()
             
            # heapq.heapify(pq)
            pq.append(query[i])
             
            # decrement the current
            # sum by the polled element
            Sum -= polled
             
            # increment sum by the
            # incoming element
            Sum += query[i]
             
            # Again maintaining the heap property
            heapq.heapify(pq)
             
        # compute the average
        max_avg = Sum/float(k)
        print(max_avg)
 
 
# Driver Code
if __name__ == '__main__':
    n = 4
    k = 3
    m = 4
    arr = [1, 2, 3, 4]
    query = [7, 2, 1, 5]
    max_average_k_numbers(n, k, m, arr, query)
 
'''This Code is written By RAJAT KUMAR'''

4.666666666666667
4.666666666666667
4.666666666666667
5.333333333333333