求kth最小元素的最大堆

Question

任务：

您有一个未排序的元素列表，在我们的例子中是整数，您必须在该列表中找到kth最小元素。当然，最明显的想法是按升序对列表进行排序，并返回kth最小元素。这应该在O(N日志N)中完成。

我试图找到kth最小的元素，我使用了一个最大堆。据我所知，当我得到kth最小元素时，我需要按递增的顺序排序数组，然后返回。如果我正确理解的话，最好使用一个Max堆来对数组进行排序，以增加排序顺序，而使用一个Min堆来查找kth最小元素。这就是不明白的地方。如何将数组按升序排序并返回kth min？如果我使用一个Max Heap，那么我在找出如何获得kth最小元素时有问题，因为等到数组被完全排序后才有意义，然后使用for循环遍历它并得到kth最小，因为这不会使HeapSort O(N log )，因为它将需要另一个for循环来遍历数组。如果我使用一个Min堆，它将是降序的。

以下是Max堆如何按递增顺序对Array进行排序：

最大堆: 10，9，8，5，1，8，3，5，5，1 8，5，8，5，1，5，3，1，9，10 5、5、5、3、1、1、8、8、9、10 5、3、1、1、5、5、8、8、9、10 1，1，3，5，5，5，8，8，9，10

我想不出怎么让kth最小。我想到了一个Min堆，因为最小的总是索引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

我试图在最大堆中找到kth最小元素。据我所知，当我得到kth最小元素时，我需要按递增的顺序排序数组，然后返回。

不，要在最大堆中找到k个小元素，我们只需要从最大堆中提取n-k元素。不需要分类。

这不会使HeapSort O( not )产生，因为它需要另一个for循环来遍历这个数组。

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

Answer 2

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

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

获得k first元素，只为这些k元素构建max-heap 。遍历所有其他元素。如果当前项小于堆顶，请移除顶部并插入当前项。在堆的末尾，顶部包含k-最小的.复杂性是N*logK。

如果你现在正在学习堆，我想这个变体更好。

执行QuickSelect算法(平均复杂度是线性的，但可能出现最坏的情况)。

Answer 3

您需要显式实现算法还是可以使用Java？如果您可以使用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]);
}