Получение 100 лучших номеров из ста миллионов номеров

Question

Один из моих друзей задал вопрос

Извлечение макс. 100 лучших номеров из ста миллионов номеров

в недавнем собеседовании. У вас есть идея найти эффективный способ ее решения?

Answer 1

@ Дарий действительно может быть улучшен !!!
"Обрезка" или откладывание операции замены кучи, как требуется

Предположим, у нас есть = 1000 на вершине кучи
Имеет родных братьев c, b
Мы знаем, что c, b> 1000

      a=1000
  +-----|-----+
 b>a         c>a




We now read the next number x=1035
Since x>a we should discard a.
Instead we store (x=1035, a=1000) at the root
We do not (yet) bubble down the new value of 1035 
Note that we still know that b,c<a but possibly b,c>x
Now, we get the next number y
when y<a<x then obviously we can discard it 

when y>x>a then we replace x with y (the root now has (y, a=1000))
=> we saved log(m) steps here, since x will never have to bubble down

when a>y>x then we need to bubble down y recursively as required

Worst run time is still O(n log m) 
But average run time i think might be O(n log log m) or something
In any case, it is obviously a faster implementation

Answer 2

int numbers[100000000000] = {...};
int result[100] = {0};
for( int i = 0 ; i < 100000000000 ; i++ )
{
    for( int j = 0 ; j < 100 ; j++ )
    {
         if( numbers[i] > result[j] )
         {
              if( j < 99 )
              {
                  memcpy(result+j+1, result+j, (100-j)*sizeof(int));
              }
              result[j] = numbers[i];
              break;
         }
    }
}