A menudo nos encontramos con este tipo de problema en el trabajo, al extraer los primeros números grandes de una cantidad grande o incluso masiva de datos. Es necesario seleccionar los 10 artículos con mayor número de clics entre los artículos masivos.
Este tipo de problema es en realidad un problema Top K.
Dados unos datos (una gran cantidad de datos N), desea encontrar los K elementos más grandes o más pequeños.
Por ejemplo: Hay mil millones de enteros largos almacenados en un archivo. ¿Cómo encontrar los 10 más grandes?
La forma más sencilla de pensar es ordenar todos los datos y luego buscar en el conjunto ordenado. La complejidad temporal del algoritmo de clasificación más rápido es generalmente O (nlogn), como la clasificación rápida. Cada tipo largo ocupa 8 bytes y mil millones de números ocuparán 7 GB de espacio de almacenamiento. Para algunas computadoras con menos de 7 GB de memoria disponible, es obvio que no se pueden leer todos los datos en la memoria al mismo tiempo para clasificarlos. De hecho, incluso si la memoria puede cumplir con los requisitos (la memoria de mi máquina es de 8 GB), este método no es eficiente, porque el propósito de la pregunta es encontrar los 10 números más grandes, pero ordenar es ordenar todos los elementos. Haz mucho esfuerzo desperdiciado.
El segundo método utiliza un montón mínimo. Primero lea los primeros 10 números para crear un montón mínimo de tamaño 10, luego repita los números siguientes y compárelos con el número superior (mínimo) del montón. Si es menor que el número más pequeño, continúe leyendo los números posteriores; si es mayor que el número superior del montón, reemplace el elemento superior del montón y reajuste el montón al mínimo. Todo el proceso continúa hasta que se hayan atravesado los mil millones de números. Luego, genere los 10 números en el montón actual de acuerdo con el método transversal en orden. La memoria utilizada por este método es controlable y solo la memoria requerida para 10 números es suficiente.