I have an array with a large number of elements, and I need to find the k largest elements.

For an idea of scale, let us assume an integer array of length 10,000,000, and k is 1,000.

I see three potential solutions:

  1. This answers to this question on Stack Overflow suggest the selection algorithm to find the kth largest integer, Then perform a partition to find all elements larger than that value.

  2. A Min Heap with a max size of 1000 could also be used. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n log k). What is the average case?

  3. I could use a selection sort algorithm to find the max k times and put it on the right of the array. This solution seems like it would have a worst case of O(n*k).

Which of these solutions would you expect to perform best on my data set?

  • 1
    Are you looking for an algorithm? Information on a min heap? While I understand what you are trying to do, I am not quite sure which aspect of the task you need help with.
    – user22815
    Commented Dec 22, 2016 at 21:59
  • @snowman I'm trying to figure out which one of the three algorithms I mentioned is best and why? Commented Dec 22, 2016 at 22:49
  • 1
    The first has O(n^2), second O(n log 1000), third O(n*1000). So what is the min of those with a given n?
    – user188153
    Commented Dec 22, 2016 at 23:54

2 Answers 2


There are a few questions to ask when dealing with large quantities of data (I leave "large" intentionally vague).

  • Can all of the data fit into memory at once?

  • Is the amount of data known up front? Or could more come in while the algorithm is processing?

  • Is it feasible to sort the data before analyzing it?

Most college-level exercises tend to deal with small amounts of data, so these questions do not matter. However, consider Google: they have massive amounts of data, and loading the entire search index into memory and sorting it is nowhere near feasible.

Even when the amount of data could fit into memory, sometimes the best solutions are ones that work in the larger case. For example, you may not need to sort this array to find the largest elements. From a theoretical perspective Big-O notation is great: however, in the real world, sometimes the fact that O(n + n log n) simplifies to O(n log n) is not a big reassurance. It could translate into minutes or hours of extra run time.

Big-O analysis:

  1. While the link you posted claims it to be O(n), as does Wikipedia, I disagree. Big-O is about worst-case complexity, which is actually O(n2). While the average-case is n (there is no letter for that), the worst-case is a huge time killer.

  2. The array is iterated once, which is O(n). Modifying the binary heap is O(log2 k), but is performed (worst case) n times. This makes the whole thing O(n + n log2k) = O(n log2k). Also keep in mind that k is small compared to n, and log2k is even smaller.

  3. Partial selection sort in this instance is O(kn).

The first option may in theory perform well most of the time, with certain data sets performing poorly.

The second option will perform very well all of the time. In the worst case, it is much better than the first algorithm. The first algorithm may outperform this one some of the time, however.

The third option is pretty much constant for a given n: the contents of the array do not matter, only its size.

I would lean toward the binary heap myself, but it might be worth analyzing whether the data would give the Quickselect algorithm a difficult time and perhaps implement both and measure their real-world speed.

  • A huge advantage of the min-heap approach is that you only need a single pass through the data. If the data is being read from a file, database, or network stream, rather than stored in memory, this could potentially be a huge factor in performance. Even if it is in memory, the cache performance of a single pass with a small-ish heap could be significant. Commented Dec 24, 2016 at 21:11

None of the ones you mentioned.

Use Quicksort, but only sort partitions recursively that contain one of the k largest elements. With your numbers, you split 10,000,000 elements into roughly two times 5 million, then the second 5 million into two times 2.5 million, and so on, until 1000 elements are left.

Takes about 2n + k log k operations if you want the k largest items in sorted order, and 2n in unsorted order. That is O(n) as long as k = O (n / log n).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.