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 -- 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.
