Saltar al contenido

Dos heaps: mediana acumulada

Lección 1 de 4 · 6 min

Dos heaps: mediana acumulada

Paso 1 de 16

Dos heaps, espalda con espalda. La mitad low guarda su mayor arriba; la mitad high, su menor. El medio vive entre ambos.

La idea

Guarda la mitad pequeña en un max-heap y la mitad grande en un min-heap. Las dos raíces quedan a cada lado del centro, así que la mediana siempre está a un vistazo, sin volver a ordenar nada.

Cada llegada entra por el lado bajo, y luego el mayor de low pasa a high. Una sola verificación de tamaño mantiene las mitades niveladas.

Ejemplo del mundo real

La balanza de dos platos de un mercado de especias. Cada pesa nueva cae en el plato izquierdo, lo más pesado de ese plato pasa al derecho, y un plato que se adelanta por dos devuelve uno. Lo que queda más cerca del pivote es el peso del medio.

El código

Te toca

¿Qué imprime esto?

import heapq
low, high = [-3, -1], [5, 9]    # low is negated: it holds 3 and 1
heapq.heappush(low, -7)
heapq.heappush(high, -heapq.heappop(low))
print(-low[0], high[0])

Mini quiz

1 / 3

¿Qué heap (montículo) guarda la mitad inferior?