Max Heap finding kth smallest elements

Question

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;
}

Answer 1

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)