Menu
What is the fastest way to find the k largest elements in an array in order (i.e. starting from the largest element to the kth largest element)?
652
To find the kth largest element, we can pass k= length(Array) – k. Now let's implement the partition method, which picks the rightmost element as a pivot, puts it at the appropriate index, and partitions the array in such a way that elements at lower indexes should be less than the pivot element.
The initial size of the priority queue is one, and it increases by at most one at each of the k – 1 steps. Therefore, there are maximum k elements in the priority queue and the time complexity of the pop and insert operations is O(log k). Thus the total time complexity is O(k * log k).
You can do it in O(n + kn) = O(n) (for constant k) for time and O(k) for space, by keeping track of the k largest elements you've seen. For each element in the array you can scan the list of k largest and replace the smallest element with the new one if it is bigger.
To find the largest element from the array, a simple way is to arrange the elements in ascending order. After sorting, the first element will represent the smallest element, the next element will be the second smallest, and going on, the last element will be the largest element of the array.
One option would be the following:
Using a linear-time selection algorithm like median-of-medians or introsort, find the kth largest element and rearrange the elements so that all elements from the kth element forward are greater than the kth element.
Sort all elements from the kth forward using a fast sorting algorithm like heapsort or quicksort.
Step (1) takes time O(n), and step (2) takes time O(k log k). Overall, the algorithm runs in time O(n + k log k), which is very, very fast.
Hope this helps!
96
C++ also provides the partial_sort algorithm, which solves the problem of selecting the smallest k elements (sorted), with a time complexity of O(n log k). No algorithm is provided for selecting the greatest k elements since this should be done by inverting the ordering predicate.
For Perl, the module Sort::Key::Top, available from CPAN, provides a set of functions to select the top n elements from a list using several orderings and custom key extraction procedures. Furthermore, the Statistics::CaseResampling module provides a function to calculate quantiles using quickselect.
Python's standard library (since 2.4) includes heapq.nsmallest() and nlargest(), returning sorted lists, the former in O(n + k log n) time, the latter in O(n log k) time.
45
answered Sep 21 '22 11:09
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
