最大堆找到第 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 个最小元素时，我需要按递增顺序对数组进行排序，return。如果我理解正确的话，最大堆最好用于按递增顺序对数组进行排序，而最小堆则用于查找第 k 个最小元素。这是不明白的地方。如何按升序对数组进行排序以及 return 第 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

如果 k 相对于堆大小 N 较小，那么从 Max 堆中检索第 k 个最小值是相当长的任务 - 它需要O((N-k)*logN)~O(N*logN) 时间 (N-k) 提取顶级元素。

为了解决问题本身——从未排序的列表中获取最小的 k，你不需要完全排序，不需要构建完整的堆。

变体 1) 获取 k 个第一个元素，为这 k 个元素构建 max-heap 。遍历所有其他元素。如果当前项目小于堆顶，移除顶部并插入当前项目。最后堆顶包含最小的 k。复杂度为 N*logK。

如果你现在正在研究堆，我想这个变体更可取。

变体 2) 执行 QuickSelect 算法（平均复杂度是线性的，但可能会出现最坏的情况）

Answer 2

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)

Answer 3

您需要明确实现算法还是可以使用 Java API？如果您可以使用 API，则可以使用 Arrays.sort() 轻松完成。为了简单起见，我省略了条件测试 k < arr.lenght。

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

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

Max Heap finding kth smallest elements

java

arrays

sorting

algorithm

heap