Max Heap finding kth smallest elements

Assignment:

You have an unsorted list of elements, in our case integers, and you must find the kth smallest element in that list. The obvious idea is of course to sort the list in ascending order and return the kth smallest element. This should be done in O(N Log N).

I am trying to find the kth smallest element which I use a Max Heap for. As I understand I need to sort the Array in increasing order and return when I get the kth smallest element. If I understand correctly a Max Heap is best to use to sort the Array in an increasing order, but a Min Heap for finding the kth smallest element. This is where don't get it. How can I sort the Array in ascending order and also return the kth min? I am having a problem finding out how to get the kth smallest element if I use a Max Heap as it would not make sense to wait until the Array is fully sorted, then traverse it with a for loop and get the kth smallest, as that would not make HeapSort O(N log N) since it would require another for loop to traverse the Array. And if I use a Min heap it would be descending order.

This is how the Max Heap is sorting the Array in increasing order:

Max Heap is made: [10, 9, 8, 5, 1, 8, 3, 5, 5, 1]

[9, 5, 8, 5, 1, 8, 3, 1, 5, 10]

[8, 5, 8, 5, 1, 5, 3, 1, 9, 10]

[8, 5, 5, 5, 1, 1, 3, 8, 9, 10]

[5, 5, 5, 3, 1, 1, 8, 8, 9, 10]

[5, 3, 5, 1, 1, 5, 8, 8, 9, 10]

[5, 3, 1, 1, 5, 5, 8, 8, 9, 10]

[3, 1, 1, 5, 5, 5, 8, 8, 9, 10]

[1, 1, 3, 5, 5, 5, 8, 8, 9, 10]

[1, 1, 3, 5, 5, 5, 8, 8, 9, 10]

I can't figure out how to get the kth smallest. I though about a Min Heap because the smallest is always index 0, but that is used for making a decreasing array?

This is my method which is a Heapsort. It calls buildHeap, and then does the sorting.

//Find kth smallest element-----------------------------------------------------------------------------------------
private int[] findKthSmallestElement(int[] arr, int kthElement) {
    buildheap(arr);
    System.out.println("Max Heap is made: " + Arrays.toString(arr));

    if(kthElement > arr.length){
        System.out.println("Number does not exist.");
        return arr;
    }
    else if(kthElement == arr.length){
        System.out.println(kthElement + " st/nd/th smallest element number" + " is: " + arr[0]);
        return arr;
    }

    heapSize = arr.length - 1;

    for(int i = heapSize; i > 0; i--) {

        swapCurrentNodeWithMaxChild(arr,0, i);

        heapSize--;

        percolateDown(arr, 0,heapSize);

        System.out.println(Arrays.toString(arr));
    }

    return arr;
}

3 answers

  • answered 2018-11-08 08:23 MBo

    If k is small relative to heap size N, then retrieving of k-th smallest from Max Heap is rather long task - it requires O((N-k)*logN)~O(N*logN) time for (N-k) extractions of top elements.

    To address problem itself - to get k-smallest from unsorted list, you don't need full sorting, don't need to build full heap.

    Variant 1) Get k first elements, build max-heap only for these k elements. Traverse all other elements. If current item is smaller than heap top, remove top and insert current item. At the end heap top contains k-smallest. Complexity is N*logK.

    I suppose that this variant is preferable if you are studying heaps now.

    Variant 2) Perform QuickSelect algorithm (average complexity is linear but the worst case might occur)

  • answered 2018-11-08 08:35 Andriy Berestovskyy

    I am trying to find the kth smallest element in a Max Heap. As I understand I need to sort the Array in increasing order and return when I get the kth smallest element.

    No, to find the k-th smalles element in a Max Heap, we just need to extract n-k elements from the Max Heap. No sorting is needed.

    that would not make HeapSort O(N log N) since it would require another for loop to traverse the Array.

    We don't need to sort the array, but as a side note one loop to traverse the Array does not change anything, since O(N log N + N) == O(N log N)

  • answered 2018-11-08 09:34 EduSanCon

    Do you need explicitly implement the algorithms or you can use Java APIs? If you can use APIs it could be easily done with Arrays.sort(). I'm omitting the conditions testing k < arr.lenght for the sake of simplicity.

    public void khtElement(k){
        int[] elements = new int[]{10, 9, 8, 5, 1, 8, 3, 5, 5, 1};
    
        Arrays.sort(elements);
        System.out.println(elements[k-1]);
    }