Find the largest 100 numbers from 1 billion integers
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (3829)

Suppose you are given 1 billion \( (1\times 10^{9}) \) unsorted integers on one disk file. How would you determine the largest 100 numbers?

Posted Answers

The algorithm works as :

  • Create a min heap with the first 100 numbers.
  • From the remaining unsorted array take each element at a time, insert it into the min heap into its correct position (heapify) and delete the root (minimum value) from the min heap.
  • Repeat the last step until the end of the remaining unsorted integers.
  • Now the heap contains the largest 100 numbers.

Time complexity = \( O(nlogm) \).
where n = Total number of integers in the unsorted array;
m = heap size (Here m=100 ).

You need to Sign In to post your solution.