Mediante el uso de dos montones, un montón mínimo (para almacenar la mitad más grande) y un montón máximo (para almacenar la mitad más pequeña). Existen varias estrategias de inserción. Aquí hay uno de ellos:
Siempre inserte en el montón máximo. Si el tamaño del montón máximo llega a ser mayor que el del montón mínimo en dos, saque el elemento máximo del montón máximo e insértelo en el montón mínimo. De lo contrario, verifique si el elemento max en el montón máximo es mayor que el elemento min en el montón mínimo. Si es así, cámbielos.
Si sigue esta estrategia, se puede encontrar la mediana mirando solo los elementos superiores en los dos montones (solo el montón máximo si el número total de elementos es impar), por lo tanto, en tiempo constante. Sin embargo, cada inserción ahora toma tiempo logarítmico.
Hacer un seguimiento de la mediana es mucho más complicado si también se permite eliminar los elementos. Ambos casos se analizan aquí: mediana de una lista dinámica
- ¿Qué es el algoritmo de Quora y cómo funciona?
- ¿Por qué utilizar el árbol de búsqueda ternario en lugar de reemplazar cada nodo de Trie a un árbol BST?
- ¿Qué otro género o sabores de la música se pueden programar algorítmicamente aparte de la música clásica?
- ¿Cuál es tu recurso favorito para aprender sobre programación competitiva?
- ¿Hay alguna guía sobre el uso de datos sintéticos para entrenar algoritmos de visión por computadora? ¿Hay alguna investigación al respecto?
