Here u r using extra space to store count values..
---------------------------------------- CHERUVU JAANU REDDY M.Tech in CSIS On Tue, May 18, 2010 at 7:01 PM, Jagadish M <jagadis...@gmail.com> wrote: > > On May 18, 8:29 am, Terence <technic....@gmail.com> wrote: > > How do you maintain the heap? Could you explain in detail for the > > following example: > > 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) > > Basically, in each node we maintain the key and its count. > > Initially, heap has the first element. > 1:1 > > Search for 2 and insert( since its not found) > 1:1 > / > 2:1 > > Search for 3 and insert ( since its not found). > > 1:1 > / \ > 2:1 3:1 > > Search for 3; since 3 is already there increment its count by 1. > > 1:1 > / \ > 2:1 3:2 > > Search for 2; since 2 is already there increment its count by 1. > > 1:1 > / \ > 2:2 3:2 > > and so on... > > > Since, there are only k distinct keys the heap size will at most be k; > so each search/insert/increment operation takes O(log k) time. > > > Jagadish > http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> > > > > > > > On 2010-5-17 22:38, Jagadish M wrote: > > > > > > > > > The best algorithm I can think of is to maintain a heap of k elements. > > > Takes O(n log k) time. > > > Is anything told about the values of the keys? If the keys have values > > > less than N, then it is possible to do > > > what you say, i.e sort them in place. > > > > > -Jagadish > > >http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> > > > > > On May 13, 7:06 pm, divya<sweetdivya....@gmail.com> wrote: > > > > >> This problem was asked in google phone interview. We have N element > > >> array with k distinct keys(No relation between k& N given so assume > > >> k<N) > > >> What is the best method to sort this array without using any extra > > >> memory? Please elaborate. > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > > >> To post to this group, send email to algoge...@googlegroups.com. > > >> To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > > >> For more options, visit this group athttp:// > 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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > > For more options, visit this group athttp:// > 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
