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.