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