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

Question

作业：

您有一个未排序的元素列表，在我们的例子中是整数，您必须找到该列表中第 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;
}

Answer 1

我试图找到最大堆中的第 k 个最小元素。据我了解，我需要按升序对数组进行排序，并在获得第 k 个最小元素时返回。

不，要找到最大堆中的第 k 个小元素，我们只需要从最大堆中提取

n-k

元素即可。无需排序。

这不会使 HeapSort O(N log N)，因为它需要另一个 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-smallest，您不需要完全排序，不需要构建完整堆。

变体 1) 获取

k

第一个元素，仅针对这 k 个元素构建 max-堆。遍历所有其他元素。如果当前项小于堆顶，则删除堆顶并插入当前项。最后堆顶包含 k 个最小的。复杂性是N*logK

。 

我想如果你现在正在研究堆，这个变体是更好的选择。

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

Answer 3

您需要显式实现算法还是可以使用 Java API？ 如果您可以使用 API，则可以使用 Arrays.sort() 轻松完成。我省略了条件测试 k

< arr.lenght for the sake of simplicity.

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

Answer 4

使用Java的PriorityQueue：

static int kthSmallest(int[] a, int n, int k) { // k = 3

     //Min Heap
    Queue<Integer> heap = new PriorityQueue<>();

    //Max Heap
    /*
      Queue<Integer> heap = new PriorityQueue<>. 
      (Collections.reverseOrder());
     *///kth largest element
    
    for(int i = 0; i < n; i++)
        heap.add(arr[i]);

    for(int j = 0; j < k-1; j++){
        System.out.println((j+1)+"th smallest element ="+heap.peek());
        heap.poll();
    }
    int kthSmallest = heap.poll();
    return kthSmallest;
}