Finding the K-th largest element in an array using a tournament tree

Question

Below, I have designed a function tournamentTreeKSelection which simulates a tree like structure using arrays and returns the largest element in the array. For example, given an input array [10,9,8,7,6,5,4,3,2,1] the following steps are performed to return 10.

[10, 8, 6, 4, 2, -1]
[10, 6, 2, -1]
[10, 2]
[10]  //Max element of array found

My goal is to now add a second parameter int k requesting that the function return the k-th largest element such that tournamentTreeKSelection(data, 2) returns 9.

I'm having a lot of difficulty in modifying my algorithm to perform this task because my assumption is that i'm going to have to keep track of all elements that the max element beats ? Any help is appreciated.

import java.util.ArrayList;
import java.util.Arrays;

public class TournamentTree {

public static int tournamentTreeKSelection(int[] data, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();

        for(int i = 0; i < data.length - 1; i += 2) {
            list.add(max(data[i] , data[i + 1]));
        }

        for(int i = 0; i < data.length - 1; i++) {
            list2.add(min(data[i], data[i + 1]));
        }

        if(list.size() == 1) return list.get(0);

        if(list.size() % 2 != 0) list.add(-1);

        if(k == 1) return tournamentTreeKSelection(listToArray(list),k);
        else return tournamentTreeKSelection(listToArray(list2), --k);
}

public static int max(int a, int b) {
    return a > b ? a : b;
}

public static int min(int a, int b) {
    return a > b ? b : a;
}

public static int[] listToArray(ArrayList<Integer> arr) {
    int[] arr2 = new int[arr.size()];
    for(int i = 0; i < arr.size(); i++)
        arr2[i] = arr.get(i);

    return arr2;
}


}

I have now modified the code but it only works for k = 1 - 8, why does it break down ? tournamentTreeKSelection(data, 9) and tournamentTreeKSelection(data, 10) return 3 when they should be returning 2 and 1 respectively.

Answer 1

First of all, why your code is wrong:

• When the size of the list is 2 or 3, your statement list.size() == 1 will be true even if K > 1.

• Why do you do min(data[i], data[i + 1]), I have a feeling you just want to remove the maximum element but what with the case [10,1,9,2,8,3,7,4,6,5], gives after 1 iteration [1,1,2,2,3,3,4,4,5] removing possible outcomes 9, 8, 7 and 6.

Some tips

• Don't do useless computations. You are calculating the two lists, while you know in front you are only going to use one of them.
• Use builtin methods whenever possible, see Math.max, Math.min
• Note that you know the size of the resulting array in front. There is no need to create an ArrayList which causes a lot of overhead for you. Just create an array of the resulting size. For k==1, ((data.length+1)/2) else data.length-1

Still wondering

You say your tournament tree structure is a requirement, but you are looping over it in your code as it is an array. Why? You could determine the max value from the moment K==1 in 1 loop, instead of taking half of the maxes and doing it over and over again.

Alternative approach

As already suggested the sorting approach, or the quick find methods can be used. I was thinking how you could still use your tournament tree approach. And the best I came up with is how merge sort works. I slightly edited because you only need max K elements to return.

public static int find(int[] a, int k) {
    int[] max = find(a, 0, a.length - 1, k);
    return max[k-1];
}
private static int[] find(int[] a, int lo, int hi, int k) {
    if (hi < lo){
        return new int[]{};
    }
    if(lo == hi){
        return new int[]{a[lo]};
    }
    int mid = lo + (hi - lo) / 2;
    int[] left = find(a, lo, mid, k);
    int[] right = find(a, mid + 1, hi, k);
    return merge(left, right, k);
}
private static int[] merge(int[] left, int[] right, int k) {
    int[] res = new int[Math.min(k, left.length+right.length)];
    int l = 0, r = 0;
    for (int i = 0; i<res.length;i++) {
        if (l == left.length)
            res[i] = right[r++];
        else if (r == right.length)
            res[i] = left[l++];
        else if (left[l] > right[r])
            res[i] = left[l++];
        else
            res[i] = right[r++];
    }
    return res;
}