Build MAX-HEAP for first 1 million integers. For next elements in the array, if ele < root node value, replace ele with root node value and apply MAX-HEAPIFY
Time Complexity : NlogK , where N is total no of elements and K is the size of heap. Here N is 1 trillion and K is 1 million Space Complexity : O(K) On Tue, Sep 1, 2009 at 6:29 PM, ankur aggarwal <[email protected]>wrote: > > * Q.3: 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. > > > > -- Shishir Mittal Ph: +91 9936 180 121 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
