@Ankit Simplify what @Dave had said:
1.you build a max heap with first k numbers 2. always compare array[k+n] where n=1.....array.size-k if array[k+n] >= k, compare next element in the array else replace top with array[k+n] and heapify so the worst case is like @Dave gave: O((N-5) * log k). in the real case, very likely you get better coz for many numbers in the array, you don't have to go down the heap for comparison On Mar 24, 12:22 am, 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. -- 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.
