2

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 Dec 22 '16 at 21:59
  • @snowman I'm trying to figure out which one of the three algorithms I mentioned is best and why? – user3795202 Dec 22 '16 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? – qwerty_so Dec 22 '16 at 23:54
4

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. – Jeremy West Dec 24 '16 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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