Java 中使用 PriorityQueue 的第 k 个最小数的时间复杂度

Question

我正在尝试解决热门面试问题Find the k-th smallest number in an array of distinct integers。我阅读了一些解决方案，发现堆数据结构非常适合这个问题。

因此，我尝试使用 Collections 框架的 PriorityQueue class 实现一个解决方案，假设它在功能上与堆相同。

这是我试过的代码：

public static int getKthMinimum(int[] input, int k){
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

    // Total cost of building the heap - O(n) or O(n log n) ?
    for(int num : input){
        heap.add(num);      // Add to heap - O(log n)
    }

    // Total cost of removing k smallest elements - O(k log n) < O(n) ?
    while(k > 0){
        heap.poll();        // Remove min - O(log n)
        k--;
    }
    return heap.peek();     // Fetch root - O(1) 
}

基于 docs，poll 和 add 方法需要 O(log n) 时间，而 peek 需要常数时间。

while 循环的时间复杂度是多少？（我认为 O(k log n)）。
为了这个问题的目的，是否应该将 O(k log n) 视为高于 O(n)？有切换的门槛吗？
这段代码的总时间复杂度是多少？会是 O(n) 吗？
如果不是 O(n)，有没有办法在 O(n) 中解决它，同时使用 PriorityQueue class？

Answer 1

1. What will be the time complexity of the while loop? (I think O(k log n)).

O(k log n) 是正确的。

2. Should O(k log n) be considered higher than O(n) for the purpose of this question? Is there a threshold where it switches?

你不能这么想。 k 可以是 0 到 n−1 之间的任何值，这意味着 k log n 可以是 0 到 n log n.

之间的任何值

3. What will be the total time complexity of this code? Will it be O(n)?

O(n log n)，因为这是构建堆的成本.

可以在 O(n) 时间内构建堆，但您的代码不会那样做；如果是这样，您的总复杂度将是 O(n + k log n) 或者，等价地，O(MAX(n, k log n)).

4. If not already O(n), is there a way to solve it in O(n), while using the PriorityQueue class?

没有。在最坏情况下 O(n) 时间存在 selection algorithms，但它们有点复杂，而且它们不使用 PriorityQueue.

最快的基于 PriorityQueue 的解决方案需要 O(MAX(n, n log MIN(k, n−k))) 时间。（关键是在迭代时只保留堆中的 k 最小元素——或者 n−k 最大的元素并使用最大堆，如果 k 足够大是值得的。）

Java 中使用 PriorityQueue 的第 k 个最小数的时间复杂度

Time complexity of k-th smallest number using PriorityQueue in Java

java

algorithm

collections

priority-queue

time-complexity