Thanks dave.. :-) On Thu, Mar 24, 2011 at 10:54 AM, Dave <[email protected]> wrote: > @Ankit: You read in the first k numbers and form a max-heap of these > numbers. This takes O(k) space. Then you read the rest of the file one > number at a time. If the number is greater than the root of the max > heap, then it is not one of the k smallest numbers. If it less than > the root, replace the root with the smaller number and re-establish > the heap condition. Thus, the memory requirement remains O(k). When > you reach the end of the data, then the heap contains the k smallest > numbers. If there are N numbers in the file, the work is O(N * log k). > > Dave > > On Mar 23, 11:22 pm, Ankit Sinha <[email protected]> wrote: >> Guys, >> >> My intention was to understand how to manage max heap of k size into >> memory. Means we have millions of numbers that we can't load into RAM >> then how in the very first go we going to load only k size and how >> will track of rest numbers. Can anybody code it? Do we need file to >> store million numbers and then read say first k numbers and then take >> another chunk? >> >> Thanks, >> >> Ankit!! >> >> >> >> On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar <[email protected]> >> wrote: >> >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of... >> >> > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma <[email protected]> >> > wrote: >> >> >> @dave -was this a constraint since the beginning? In case it was, I am >> >> sorry I didn't notice. >> >> >> In that case, the heap method ought to work better. I dont think the >> >> quicksort method will work. >> >> >> Sent from my iPhone >> >> >> On 20-Mar-2011, at 23:00, Dave <[email protected]> wrote: >> >> >> > @Natansh: How do you do this with the constraint that your RAM is so >> >> > small that you cannot accomodate all of the numbers at once? >> >> >> > Dave >> >> >> > On Mar 20, 9:04 am, Natansh Verma <[email protected]> wrote: >> >> >> There's another way... use the partitioning method for quicksort to >> >> >> find the >> >> >> k smallest elements. Then it should take expected time as O(n + klogk). >> >> >> Plus, it is in-place. >> >> >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit <[email protected]> wrote: >> >> >>> I agree with munna >> >> >> >>> -- >> >> >>> 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.-Hide quoted text - >> >> >> >> - Show quoted text - >> >> >> > -- >> >> > 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. >> >> >> -- >> >> 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. >> >> > -- >> > Thank You >> > Rajeev Kumar >> >> > -- >> > 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.- Hide quoted text - >> >> - Show quoted text - > > -- > 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. > >
-- 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.
