Heap maintains the word and frequency count On 5/18/10, 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) > > 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 >> >> >> 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. >>> 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. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > >
-- -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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.