@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 <akki12...@gmail.com> 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 <rajeevprasa...@gmail.com> > wrote: > >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of... > > > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma <natansh.ve...@gmail.com> > > 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 <dave_and_da...@juno.com> 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 <natansh.ve...@gmail.com> 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 <lipu...@gmail.com> 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 algogeeks@googlegroups.com. > >> >>> To unsubscribe from this group, send email to > >> >>> algogeeks+unsubscr...@googlegroups.com. > >> >>> 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 algogeeks@googlegroups.com. > >> > To unsubscribe from this group, send email to > >> > algogeeks+unsubscr...@googlegroups.com. > >> > 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 algogeeks@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com. > >> 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 algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
