java - get indexes of n smallest elements in an array

Question

I have an int array int[] myArray = new int[100]; and want to get indexes of smallest 10 (any n) elements. How can I do this?

Answer 1

Sorting the array and then picking 10 is simple, but it'd be O(n log n), and if you don't want to re-order the initial array, you'd need to make a copy too.

A better idea is to use a max-heap (or priority queue), which automatically sorts elements as you insert them, such that the largest element is the root node. Walk along the array, keep putting in elements until you hit 10; then, for every subsequent element, simply check if it's smaller than the biggest element in the heap (constant-time check), and if it is, pop that one out and insert the new element. When you've passed through the entire array, the 10 things left inside are your minimum elements. This'll get you your result in O(n log 10) == O(n), since each insert into the heap will only cost O(log 10).

Java's Priority Queue implementation is a min-queue by default, so you'd need to pass in a Comparator that reverses the ordering. See this question for examples on how to do that. You'd need to create a custom object that contains (value, index) pairs too, if you want to get the indices out at the end.