Find sum of K largest elements in an array

The problem statement is to write code that returns the sum of the K largest elements in a given array. The array is not sorted already.

My solution is based on the idea of quicksort, by finding pivot elements until the pivot is actually the kth element. Thus, all elements left of the pivot will be larger than the pivot.

public class Solution {

    public int getKthSum(int[] a, int k) {
        int kthIdx = getKthLargestIndex(a, k);
        int sum = 0;
        for (int i = 0; i  a[p]) {
                swap(a, i, firstHigh);
                firstHigh++;
            }
        }
        swap(a, p, firstHigh);
        return firstHigh;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {2,1};
        System.out.println(s.getKthSum(nums, 1));
        System.out.println(Arrays.toString(nums));
        int[] nums2 = {3,2,1,5,6,4};
        System.out.println(s.getKthSum(nums2, 2));
        System.out.println(Arrays.toString(nums2));

    }

Based on my testing, I believe that this implementation works. Is it more or less efficient compared to a maxHeap implementation?

While the idea is perfectly sound, there are reasons to prefer a min heap approach:

-
The min heap guarantees an \$O(n \log k)\$ time complexity. Your method
may degenerate to \$O(nk)\$ for nearly sorted data.

-
The min heap works with streaming data. Your method requires the
entire data set to be present.

-
The min heap preserves the original order. Your method rearranges
data.

You may also gain some performance with tail recursion elimination:

-
First, convert the getKthLargestIndex into really tail recursive form:

if (k == rank) {
        return p;
    if ( k < rank) {
        h = p - 1;
    }
    else {
        k -= rank;
        l = p + 1;
    }
    return getKthLargestIndex(a, k, l , h);

-
Now replace the recursion with a loop:

private int getKthLargestIndex(int[] a, int k, int l, int h) {
        while (1) {
            int p = partition(a, l, h);
            int rank = p - l +1;

            if (rank == k) {
                return p;
            }

            if ( k < rank) {
                h = p - 1;
            }
            else {
                k -= rank;
                l = p + 1;
            }
        }
    }

StackExchange Code Review Q#105307, answer score: 8