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 <j.r...@mail.cryst.bbk.ac.uk>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 >> <j.r...@mail.cryst.bbk.ac.uk >> <mailto:j.r...@mail.cryst.bbk.**ac.uk <j.r...@mail.cryst.bbk.ac.uk>>> >> 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 >> algogeeks@googlegroups.com >> <mailto:algogeeks@**googlegroups.com <algogeeks@googlegroups.com>>. >> >> To unsubscribe from this group, send email to >> algogeeks+unsubscribe@__google**groups.com <http://googlegroups.com> >> >> <mailto:algogeeks%**2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> >> **>. >> >> 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 >> algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to algogeeks+unsubscribe@** > googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. > 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 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.
