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 <abhijith200...@gmail.com>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 <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. > -- 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.
