Find K Smallest Elements in an Array

Question

I want to find the K smallest elements in an array, and I was able to basically sort my array into a min-heap structure but I am still getting the wrong output.

Here are my inputs:

arr = [9,4,7,1,-2,6,5]
k = 3

Here's the Code:

public static int[] findKSmallest(int[] arr, int k) {
    int[] result = new int[k];
    int heapSize = arr.length;
    // Write - Your - Code  

    for (int i = (heapSize - 1) / 2; i >= 0; i--) {
        minHeap(arr, i, heapSize);
    }

    for (int j = 0; j < k; j++) {
        result[j] = arr[j];
    }
    return result;
}

public static void minHeap(int[] arr, int index, int heapSize) {
    int smallest = index;
    while (smallest < heapSize / 2) {
        int left = (2 * index) + 1; // 1 more than half the index
        int right = (2 * index) + 2; // 2 more than half the index 

        if (left < heapSize && arr[left] < arr[index]) {
            smallest = left;
        }

        if (right < heapSize && arr[right] < arr[smallest]) {
            smallest = right;
        }

        if (smallest != index) {
            int temp = arr[index];
            arr[index] = arr[smallest];
            arr[smallest] = temp;
            index = smallest;
        } else {
            break;
        }
    }
}

Here is my expected output:

[-2,1,4]

Though my output is:

[-2,1,5]

Please I would like to know where I went wrong.

Answer 1

If K is relatively small to the array size my recommendation is to use selection sort, so it may be a design pattern Strategy - depending on K to array size relation with for example two procedures: selection sort for small K and quicksort for huge K. Instead of playing with design patterns good may be also simple if statement e.g. selection<=30%<quick

Answer 2

Since Java 8 we can do Sorting stream

Alternative code:

Arrays.stream(arr).sorted().boxed().collect(Collectors.toList()).subList(0, k);

where:

int[] arr = {9,4,7,1,-2,6,5};
int k = 3; // toIndex

Alternative code in context and testbench:

public static void main(String[] args) {
    int[] arr = {9, 4, 7, 1, -2, 6, 5};
    int k = 3; // toIndex

    List<Integer> listResult = Arrays.stream(arr)
            .sorted().boxed().collect(Collectors.toList()).subList(0, k);
    // print out list result
    System.out.println("Output of list result: " + listResult);


    int[] arrayResult = listResult.stream().mapToInt(i -> i).toArray();
    // print out array result
    List<String> arrayResultAsString = Arrays.stream(arrayResult)
            .boxed().map(i -> String.valueOf(i)).collect(Collectors.toList());
    System.out.println("Output of array result: " + arrayResultAsString);
}

Output:

Output of list result: [-2, 1, 4]
Output of array result: [-2, 1, 4]

Answer 3

After you build your minHeap you have to extract element and appropriately adjust tree. You simply took elements from array by index, which is not how heap works.

I slightly modified your minHeap() method to use recursion and you should check arr[smallest] < arr[left] not the orther way around.

public static int[] findKSmallest(int[] arr, int k) {
    int[] result = new int[k];
    int heapSize = arr.length;
    // Write - Your - Code

    for (int i = (heapSize - 1) / 2; i >= 0; i--) {
        minHeap(arr, heapSize, i);
    }

    // extract elements from heap
    for (int i = heapSize - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        minHeap(arr, 0, i);
    }

    for (int j = 0; j < k; j++) {
        result[j] = arr[j];
    }
    return result;
}

public static void minHeap(int[] arr, int index, int heapSize) {
    int smallest = index;
    int left = (2 * index) + 1; // 1 more than half the index
    int right = (2 * index) + 2; // 2 more than half the index
    if (left < heapSize && arr[smallest] < arr[left]) {
        smallest = left;
    }
    if (right < heapSize && arr[smallest] < arr[right]) {
        smallest = right;
    }
    if (smallest != index) {
        int temp = arr[index];
        arr[index] = arr[smallest];
        arr[smallest] = temp;
        minHeap(arr, smallest, heapSize);
    }
}

Hope this helps. As expected the result is:

[-2, 1, 4]

Answer 4

You can use Arrays.stream​(int[]) method:

int[] arr = {9, 4, 7, 1, -2, 6, 5};
int k = 3;

int[] minHeap = Arrays.stream(arr).sorted().limit(k).toArray();

System.out.println(Arrays.toString(minHeap)); // [-2, 1, 4]