use a heap u ill be using a min heap ie the Nth element will be the root.So when u find a element compare with the root if its greater then replace the root with this new number and call heapify function
On Mon, Jul 11, 2011 at 4:43 PM, abhijith reddy <[email protected]>wrote: > You can use priority_queue in STL. The size needs to be limited to N > elements. At any point the the N elements in the heap will give the largest > N > elements processed so far. > > > On Mon, Jul 11, 2011 at 4:41 PM, John Reid <[email protected]>wrote: > >> >> >> On 11/07/11 12:07, abhijith reddy wrote: >> >>> Wouldn't a heap be ideal for this ? >>> >> >> I thought it might. Do I just need to limit the heap to size 2 * N to >> avoid storing values I'll never need? >> >> Thanks, >> John. >> >> >> >>> On Mon, Jul 11, 2011 at 3:35 PM, John Reid >>> <[email protected] >>> <mailto:[email protected].**ac.uk <[email protected]>>> >>> wrote: >>> >>> I have a procedure that generates N x M values sequentially. I want >>> to store the N largest ones and discard the others. Obviously I can >>> store all the values in a vector, sort it when it is full and then >>> choose the top N values. Is there a more efficient way using a data >>> structure that just stores the top N values as the procedure goes >>> along? Typically M is 1,000 and N is anywhere from 1,000 to 50,000. >>> I have no prior expectation on how the N largest values are >>> distributed amongst the N x M values. >>> >>> I'm working in C++ with the STL and boost libraries. >>> >>> Thanks for reading this, >>> John. >>> >>> -- >>> 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] >>> <mailto:algogeeks@**googlegroups.com <[email protected]>>. >>> >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscribe@__google**groups.com <http://googlegroups.com> >>> >>> <mailto:algogeeks%**[email protected]<algogeeks%[email protected]> >>> **>. >>> >>> For more options, visit this group at >>> >>> http://groups.google.com/__**group/algogeeks?hl=en<http://groups.google.com/__group/algogeeks?hl=en> >>> >>> <http://groups.google.com/**group/algogeeks?hl=en<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 >>> algogeeks+unsubscribe@**googlegroups.com<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/**group/algogeeks?hl=en<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 algogeeks+unsubscribe@** >> googlegroups.com <algogeeks%[email protected]>. >> For more options, visit this group at http://groups.google.com/** >> group/algogeeks?hl=en <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. > -- 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.
