@Praveen: I can think of two ways you might be using the heap: 1) You transform the unordered input array into a max heap. This is O(n log n). Then, k times, you remove the top element. This is O(k log n). The total is O((k+n) log n).
2) You form a min heap of the first k elements of the array. This is O(k log k). Then, for the remaining n-k elements of the input array, you ignore an element that is less than than the root of the heap, but replace the root with a larger or equal element and reheapify. This is O(n-k) log k). The total is O(n log k). In either case, the algorithm is not O(k log n). So you must have another algorithm. Please explain it in more detail. Dave On Sep 9, 12:35 am, praveen raj <praveen0...@gmail.com> wrote: > I am considering.. > > Maxheapify... A[parent(i)]>=A[i] > kth largest element... > therefore O(klogn)... > k times u have to extract the largest element and logn to maintain the > maxheapify everytime..... > > minheapify....A[parent(i)]<=A[i] > kth largest element.... that means ... (n-k) smallest element..... > therefoe... O((n-k)logn)... > > With regards, > > Praveen Raj > DCE-IT 3rd yr -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
