¿Existe un algoritmo en línea para calcular la mediana de una secuencia de números si los elementos de la secuencia se pueden agregar o eliminar en cualquier momento?

Respuesta del usuario de Quora a ¿Existe un algoritmo en línea para calcular la mediana de una secuencia de números si los elementos de la secuencia se pueden agregar o eliminar en algún momento ?, los árboles balanceados, es lo que haría.

Una implementación estándar de almacenamiento dinámico utilizando un vector requeriría también una asignación del valor del elemento a su posición, para manejar las eliminaciones correctamente (¿un hashmap?). Los montones utilizan menos espacio que los árboles binarios de búsqueda, pero si también necesita un hashmap, puede ser demasiado grande.

Otra idea sería no eliminar elementos de un montón de forma explícita, sino agregarlos a un montón auxiliar. Luego, siempre debe comparar la parte superior de ambos montones (regular y auxiliar) para ver si la parte superior de uno normal todavía está viva. (Podría agregar algunas reglas de recolección de basura, como si el montón auxiliar tiene más del 50% de elementos, luego simplemente clasifique todo y limpie).

Otra idea solo funcionaría para un pequeño dominio de números (digamos: números del 0 al 255): solo construya un árbol binario implícito estático (similar al utilizado en una implementación de montón) de modo que cada hoja contenga el número de ocurrencias particulares número y los nodos internos almacenan sumas parciales (al igual que en la solución de Tomislav Novak). Eso usaría solo 256 * 2 enteros de memoria y consultas O (lg n) (que se pueden implementar de una manera que no requiera si las ramas: D).

Creo que también podría almacenar solo el 1/3 medio de elementos en el árbol, mientras los mantiene a la izquierda y a la derecha en hashmaps. Siempre que la mediana se acerque al límite del árbol, puede volver a calcular todo.

Sin embargo, lo que realmente me interesa es si hay algunos buenos algoritmos de transmisión que usen solo memoria constante, sin introducir errores grandes (probablemente los hay).

Una forma sencilla de hacer esto es aumentar un árbol de búsqueda binaria (equilibrado) almacenando también para cada nodo el tamaño del subárbol enraizado en ese nodo. Esto hace posible realizar todas las operaciones requeridas (insertar, eliminar y consultar el n / 2-ésimo elemento más pequeño) en O (lg n).

Puede consultar http://www.shygypsy.com/tools/bs … para ver una implementación de un árbol AVL que admita esas operaciones.

Se puede adoptar el enfoque (Método basado en montones) mencionado en el siguiente enlace,
http://www.geeksforgeeks.org/arc …

El algoritmo utilizado en el enlace anterior no eliminará elementos.

Es bastante fácil agregar nuevos elementos, sin embargo, la eliminación es complicada. El elemento que se eliminará podría estar en el montón izquierdo o derecho, y después de la eliminación necesitamos equilibrar los montones nuevamente.

EDITAR:
Me perdí de notar que es malo. He interpretado como mediana . Perdón por la publicación incorrecta.

Una de las mejores formas de determinar la mediana del flujo de números es usar la combinación de montón máximo y montón mínimo:

lógica: cree el montón máximo de todos los números mínimos y el montón mínimo de todos los números máximos, de modo que cuando se solicite una mediana se encuentren dos casos:
1. el tamaño del montón máximo es mayor que el montón mínimo, entonces el elemento superior del montón máximo contendrá la mediana.
2. el tamaño del montón máximo es igual al tamaño del montón mínimo, entonces la mediana será el promedio de los dos elementos superiores del montón máximo y el montón mínimo.

La parte crítica es cómo determinar o insertar el nuevo elemento para que la diferencia en el número de elementos en el montón mínimo y el montón máximo esté entre cero y 1.

Aquí está el pseudocódigo para insertar el nuevo elemento:

antes de seguir el código, podemos suponer que estamos utilizando la estructura de datos PriorityQueue presente en el paquete Collection en java para representar nuestro montón:

public void insertData(int data){ if(mxHeap.size()==0) mxHeap.insert(data); if(data=