radix sort would take O(nk) time in terms of the number of digits. And infact sorting is a much bigger problem than what we need. All that we need is the top k elements of an n element list.
A strategy would be to use fibonacci heaps that have O(1) Decrease key. You can construct a heap out of the first sqrt(n) elements and then compare each new element with the max in the heap. If lesser then you could decrease the key of the maximum element to the newly found value. --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
