Create a B+ tree and extract the first 100 leaf nodes.... On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg <ankurga...@gmail.com> wrote:
> U can use selection Algorithm to achieve the same ...it has got expected > running time complexity as O(n) ...Read Wikipedia to see the proper > implementation.. > > Just some tweak with Quick Sort ..Also there is one method median of > medians one which has worst case complexity as O(n) > > Regards > > Ankur > > > On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma <amolsharm...@gmail.com>wrote: > >> it will be max heap only.....in which root denotes the largest number in >> your set of 100 smallest >> -- >> >> >> Amol Sharma >> Third Year Student >> Computer Science and Engineering >> MNNIT Allahabad >> >> >> >> >> On Thu, Aug 18, 2011 at 9:14 AM, aditi garg <aditi.garg.6...@gmail.com>wrote: >> >>> @ dave : i hv one doubt,we wud be maintaining a max or a min heap?? >>> >>> >>> On Thu, Aug 18, 2011 at 9:11 AM, aditi garg >>> <aditi.garg.6...@gmail.com>wrote: >>> >>>> thank u so much dave :) >>>> >>>> >>>> On Thu, Aug 18, 2011 at 8:44 AM, Dave <dave_and_da...@juno.com> wrote: >>>> >>>>> @Aditi: Form a max-heap of the first 100 numbers. Then as you read the >>>>> remaining numbers, if a number is less than the root of the max-heap, >>>>> replace the root with it and restore the heap condition. When you >>>>> reach the end of the million numbers, the heap will contain the >>>>> smallest 100 numbers. >>>>> >>>>> If there are n numbers and you want the smallest k, this algorithm is >>>>> O(n log k). >>>>> >>>>> Dave >>>>> >>>>> On Aug 17, 10:05 pm, aditi garg <aditi.garg.6...@gmail.com> wrote: >>>>> > How to find the set of smallest 100 numbers out of 1 million >>>>> numbers... >>>>> >>>>> -- >>>>> 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. >>>>> >>>>> >>>> >>>> >>>> -- >>>> Aditi Garg >>>> Undergraduate Student >>>> Electronics & Communication Divison >>>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY >>>> Sector 3, Dwarka >>>> New Delhi >>>> >>>> >>>> >>> >>> >>> -- >>> Aditi Garg >>> Undergraduate Student >>> Electronics & Communication Divison >>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY >>> Sector 3, Dwarka >>> New Delhi >>> >>> >>> -- >>> 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. >> > > -- > 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. > -- regards Apoorve Mohan -- 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.