i agree with amol.... it cud be max-heap only... Regards, PAYAL GUPTA
On Thu, Aug 18, 2011 at 2:26 PM, Apoorve Mohan <[email protected]>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 <[email protected]>wrote: > >> Create a B+ tree and extract the first 100 leaf nodes.... >> >> On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg <[email protected]> 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 <[email protected]>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 >>>> <[email protected]>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 <[email protected] >>>>> > wrote: >>>>> >>>>>> thank u so much dave :) >>>>>> >>>>>> >>>>>> On Thu, Aug 18, 2011 at 8:44 AM, Dave <[email protected]>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 <[email protected]> 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 [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. >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> 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 [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. >>>> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> 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 [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.
