C#: Efficient algorithm to find greatest m elements in an N x N matrix

Question

Hi,

I would like to know if there's an efficient algorithm to find the greatest m elements in an N x N matrix, with a method header like this:

double[] greatestValues(double[][] matrix, int numberOfElements);

Any ideas?

Answer 1

If you treat the N x N matrix as an array of N x N items you can apply one of the following techniques:

Direct application of the quick sort based selection algorithm The quick sort based selection algorithm can be used to find k smallest or k largest elements. To find k smallest elements find the kth smallest element using the median of medians quick sort based algorithm. After the partition that finds the kth smallest element, all the elements smaller than the kth smaller element will be present left to the kth element and all element larger will be present right to the kth smallest element. Thus all elements from 1st to kth element inclusive constitute the k smallest elements. The time complexity is linear in n, the total number of elements.

Data structure based solutions Another simple method is to add each element of the list into an ordered set data structure, such as a heap or self-balancing binary search tree, with at most k elements. Whenever the data structure has more than k elements, we remove the largest element, which can be done in O(log k) time. Each insertion operation also takes O(log k) time, resulting in O(nlog k) time overall.

It is possible to transform the list into a heap in Θ(n) time, and then traverse the heap using a modified Breadth-first search algorithm that places the elements in a Priority Queue (instead of the ordinary queue that is normally used in a BFS), and terminate the scan after traversing exactly k elements. As the queue size remains O(k) throughout the traversal, it would require O(klog k) time to complete, leading to a time bound of O(n + klog k) on this algorithm.

From here.