finding the largest k numbers in an array without sorting the whole list?
Hi, I need help with my assignment.
I need to write a program to find the largest k numbers in the array.
eg. array: 12, 9, 36, 3, 0, 33
k = 3
output = 12, 36, 33
Here are the constraints:
1. I can't sort the whole list and then pick out the largest k numbers
but can sort part of the data
2. output of k largest items doesn't need to be sorted.
3. the running time should run better than O(nlogn) , n is the size of the array.
Here is what I am going to do.
1. first, pick the first k numbers in the data and store them in another array of size k, called HEAP
2. sort the HEAP of size k, which takes klogk time when using the quicksort.
3. loop over the rest n-k numbers in the original array, for each number, compare it to the smallest number in the HEAP array, if smaller than it, discard it, if larger than it, update the smallest number in the HEAP array with this number.
4. If after the updating, the order of the numbers in the HEAP array has changed, then resort them, resorting takes logk time when using heap sort. (I am not sure about the running time here...)
5. then worst case running time should be klogk + (n - k) * klogk = nlogk <= nlogn
but using this implementation, the k largest numbers will be sorted at the end. My question is that is there any better way to do it without sorting anything? or the largest k numbers are not sorted at the end?
Sorry for the long description. Thanks in advance.