¿Cuál es la mejor forma de obtener los k elementos mayores de un flujo de n números?
Opciones
- Ordenar primero los n números: O(n log n)
- Mantener un min-heap de tamaño k: O(n log k) (Opción correcta)
- Meter los n en un max-heap y sacar k
- Recorrer los números k veces: O(nk) en total
Respuesta
Mantener un min-heap de tamaño k: O(n log k)
Por qué
Un heap es una estructura que siempre te da su elemento menor en O(1) y añade o quita en O(log tamaño).
Mantén un min-heap con los k mayores números vistos hasta ahora. Por cada número nuevo, añádelo; si el heap tiene más de k elementos, saca el menor.
El heap nunca supera k, así que el coste es O(n log k), y la memoria es solo O(k). Python: heapq.nlargest(k, numbers).
Recuerda
Top k → heap de tamaño k.