Largest 100

There is a big file containing 10^8 integers, one per line. Devise an algorithm to find the largest 100 integers among them. Remember you cannot read all of them into memory at once.

Solution :

We simply use Min-Heap data structure to keep list of top 100 numbers replacing next with lowest if greater.

Code :

/**
 *  Assume standard heap ADT operations : heap_min(), heap_remove() and heap_insert()
**/

void top_100(FILE *fp, int output[]){

int num, count=0;

while(fscanf(fp, "%d\n", &num)){

if(++count > 100 && num > heap_min(output)){

heap_remove(output);

}
heap_insert(output, num);

}

}

Complexity :

• Time : O(N log N)
• Space : O(1)