On 12/07/11 16:15, bittu wrote:
John You Can Use MinHeap
here is the algo
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of
the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]),
compare it with root of MH.
a) If the element is greater than the root then make it root and call
heapify for MH
b) Else ignore it.
O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth
largest element.
Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted
output is needed then O(k + (n-k)Logk + kLogk)
Thanks
Shashank
Computer Science
Birla Institute of Technology Mesra
Thanks everyone for all the replies. Sorry for basic question, I am
feeling a little slow!
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
