El método de Anon mencionado anteriormente es bastante simple y directo; solo tiene que mantener una lista ordenada de elementos en todo momento; es decir, inserte el elemento entrante en el lugar correcto y simplemente seleccione la mediana de la lista ordenada (o el promedio de dos números medios).
Por otro lado, si le preocupa la eficiencia, sugeriría el método max-heap min-heap.
La idea clave detrás de este enfoque es mantener dos montones: un montón mínimo y un montón máximo, de modo que todos los elementos menores que la raíz del montón máximo se almacenen en el montón máximo y todos los elementos mayores que la raíz del montón mínimo se almacenan en el montón mínimo. Además, la raíz de min-heap> = raíz de max-heap. Finalmente, asegúrese de que el número de elementos en ambos montones difiera como máximo 1. De esta manera, la raíz del montón con más elementos es siempre la mediana, si # de elementos son iguales, entonces el promedio de los elementos raíz es la mediana .
- ¿Qué significa el multiplicador de Lagrange en el informe de sensibilidad de Excel?
- ¿Cuáles son las 15 mejores universidades públicas de investigación para estudiantes de matemáticas?
- ¿Existen pruebas no probabilísticas de conocimiento cero?
- Si comenzamos con solo 2 humanos de hace 100,000 años y aumentamos la población un 1% cada año, ¿cuál será la población de la tierra hoy?
- Cómo probar la 'función discontinua' de Dirichlet
Algoritmo
- Inicialice dos montones: min-heap y max-heap sin elementos
- Para, cada número entrante ‘n’:
- Identificar a qué montón debería pertenecer: en función de si el elemento es menor que la raíz del montón máximo o mayor que la raíz del montón mínimo, de lo contrario, los montones están bien
- Insértelo en el montón relevante, equilibre el montón
- Vuelva a equilibrar las longitudes del montón: Por lo tanto, si el número de elementos en uno de los montones excede el número de elementos en el otro en más de 1, elimine el elemento raíz de este montón e insértelo en el otro montón y equilibre.
- Identifica la mediana mirando las raíces de los árboles. Por. por ejemplo, si la raíz en min-heap = 6, la raíz en max-heap = 5 y el número de elementos en ambos árboles son iguales, entonces mediana = 5.5, de lo contrario si el número de elementos en min-heap> max-heap => mediana = 6.
Ejemplo:
Configuración inicial de montones
A partir del ejemplo que ha considerado, los montones pueden verse así:
Árbol izquierdo = montón máximo, Árbol derecho = montón mínimo
Insertar un elemento en el montón apropiado
Veamos, qué sucede si obtienes un nuevo número, digamos 5:
Claramente, es menor que la raíz de max-heap, por lo que debemos insertarlo allí.
Simplemente agréguelo a la primera hoja disponible en el árbol.
Equilibrio del montón relevante
Ahora, cambie sucesivamente hasta que cada padre sea mayor que sus hijos (en caso de min-montón, la condición se invierte; es decir, cambie hasta que cada padre sea más pequeño que sus hijos)
Encontrar la mediana
Ahora, vemos que la diferencia en # de elementos = 1, max-heap tiene más elementos, por lo tanto, mediana = raíz del max-heap = 6
Complejidad espacio-tiempo
Para el enfoque de almacenamiento dinámico, la inserción y el equilibrio toman O (log n). Buscando la mediana es O (1).
Mientras que, para el método de inserción-clasificación, el punto de inserción se puede encontrar usando la búsqueda binaria que toma O (log n), pero necesitará cambiar todos los datos, lo que le da el peor de los casos de O (n) operaciones
2. Ahora, imagine cada escenario donde agrega un nuevo entero, “n”. “n” puede ser mayor o menor que 6.5. (¡No puede ser igual a 6.5, porque 6.5 no es un entero!) 
Como se muestra arriba, ahora hay un número “obvio medio” si cuenta la distribución en ambos lados: hay 3 valores a la “izquierda” de 6 y 3 a la “derecha” de 6. Entonces 6 es una mediana posible cuando agrega un nuevo entero, “n”. 
