i agree with amol.... it cud be max-heap only... Regards, PAYAL GUPTA
On Thu, Aug 18, 2011 at 2:26 PM, Apoorve Mohan <apoorvemo...@gmail.com>wrote: > or rather u can just have 100 iterations of selection sort...u'll get the > min 100 iterations...and this is inplace as well... > > > On Thu, Aug 18, 2011 at 1:18 PM, Apoorve Mohan <apoorvemo...@gmail.com>wrote: > >> 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 >> >> > > > -- > 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. > -- 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.
