Find k max integers of an array -- Min Heap vs. Selection Algo vs. Selection Sort

Question

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?

Answer 1

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(n²). 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(log₂ k), but is performed (worst case) n times. This makes the whole thing O(n + n log₂k) = O(n log₂k). Also keep in mind that k is small compared to n, and log₂k 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.