java - 最大堆找到第 k 个最小元素

Question

作业:

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).

我试图找到我使用最大堆的第 k 个最小元素。据我了解，我需要按递增顺序对数组进行排序，并在获得第 k 个最小元素时返回。如果我理解正确的话，最大堆最好用于按递增顺序对数组进行排序，而最小堆则用于查找第 k 个最小元素。这是不明白的地方。如何按升序对数组进行排序并返回第 k 分钟？如果我使用最大堆，我在找出如何获得第 k 个最小元素时遇到问题，因为等到数组完全排序后，然后用 for 循环遍历它并获得第 k 个最小元素是没有意义的，因为不会使 HeapSort O(N log N) 因为它需要另一个 for 循环来遍历数组。如果我使用最小堆，它将按降序排列。

这就是最大堆如何按升序对数组进行排序:

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]

我不知道如何得到第 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;
}

Answer 1

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.

不需要，要找到最大堆中的第k小元素，我们只需要从最大堆中提取n-k个元素即可。无需排序。

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

我们不需要对数组进行排序，但作为旁注，遍历数组的一个循环不会改变任何东西，因为 O(N log N + N) == O(N log N)