Max Heap: поиск k-х наименьших элементов ⇐ JAVA

[Anonymous]

Присваивание:

У вас есть несортированный список элементов, в нашем случае целых чисел, и вы должны найти k-й наименьший элемент в этом списке. Очевидная идея, конечно, состоит в том, чтобы отсортировать список в порядке возрастания и вернуть k-й наименьший элемент. Это должно быть сделано за O(N Log N).

Я пытаюсь найти k-й наименьший элемент, для которого я использую максимальную кучу. Насколько я понимаю, мне нужно отсортировать массив в порядке возрастания и вернуть результат, когда я получу k-й наименьший элемент. Если я правильно понимаю, максимальную кучу лучше всего использовать для сортировки массива в порядке возрастания, а минимальную кучу - для поиска k-го наименьшего элемента. Вот тут не пойми. Как я могу отсортировать массив в порядке возрастания, а также вернуть k-ю минуту? У меня возникла проблема с выяснением того, как получить k-й наименьший элемент, если я использую максимальную кучу, поскольку не имеет смысла ждать, пока массив будет полностью отсортирован, а затем пройти его с помощью цикла for и получить k-й наименьший элемент, поскольку это не сделает HeapSort O(N log N), поскольку для обхода массива потребуется еще один цикл for. И если я использую минимальную кучу, она будет в порядке убывания.
Вот как максимальная куча сортирует массив в порядке возрастания:
Максимальное количество кучи составляется: [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]

Не могу понять, как получить k-е число самый маленький. Я думал о минимальной куче, потому что наименьший индекс всегда равен 0, но он используется для создания уменьшающегося массива?
Это мой метод, который представляет собой пирамидальную сортировку. Он вызывает buildHeap, а затем выполняет сортировку.
//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;
}


Подробнее здесь: https://stackoverflow.com/questions/532 ... t-elements