Trade-offs

Top-k: el heap del tamaño justo

Tienes que encontrar las 10 canciones más escuchadas entre 100 millones de reproducciones agregadas por canción (un millón de canciones distintas).

Los totales de las canciones llegan en un flujo, una canción tras otra, y solo puedes guardar en memoria unas pocas. ¿Qué enfoque usas para quedarte con las 10 más escuchadas?Un min-heap de tamaño 10: cada canción se compara con la raíz y la reemplaza si es mayorUn max-heap con todas las canciones, extrayendo 10 veces: construirlo es O(n)Un max-heap de tamaño 10: cada canción se compara con la raíz, la mayor de las 10Ordenar el millón de canciones y tomar las 10 primeras, en O(n log n)