Form the first million numbers into a max-heap, where the largest number at the root. Any number in the input file that is larger than the root can be ignored. If it is smaller than the root, replace the root with the number and trickle it down the heap to restore the heap condition. Worst case is if the file is in descending order, in which case, there are about 2 * 0.999999 trillion * log_2(1 million) data comparisons.
Dave On Jun 23, 7:18 am, amit <[email protected]> wrote: > Given a set of 1 Trillion integers on hard disk, find the smallest 1 > million of them. You can fit at most 1 million integers in memory at a > time. State the fastest solution you can think of. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
