@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 <[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. -- 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.
