使用堆查找第K大元素的时间复杂度

Question

我有一些不同的代码实现，用于在未排序的数组中查找第 K 大元素。我使用的三个实现都使用 min/max 堆，但我无法计算其中一个的运行时复杂性。

实施 1：

int findKthLargest(vector<int> vec, int k)
{
    // build min-heap
    make_heap(vec.begin(), vec.end(), greater<int>());

    for (int i = 0; i < k - 1; i++) {
        vec.pop_back();
    }

    return vec.back();
}

实施 2：

int findKthLargest(vector<int> vec, int k)
{
    // build max-heap
    make_heap(vec.begin(), vec.end());

    for (int i = 0; i < k - 1; i++) {
        // move max. elem to back (from front)
        pop_heap(vec.begin(), vec.end()); 
        vec.pop_back();
    }

    return vec.front();
}

实施 3：

int findKthLargest(vector<int> vec, int k)
{
    // max-heap prio. q
    priority_queue<int> pq(vec.begin(), vec.end());

    for (int i = 0; i < k - 1; i++) {
        pq.pop();
    }

    return pq.top();
}

根据我的阅读，我假设第二个的运行时间是 O(n) + O(klogn) = O(n + klogn)。这是因为构建最大堆是在 O(n) 中完成的，如果我们这样做，弹出它需要 O(logn)*k 'k' 次。

但是，这就是我感到困惑的地方。对于第一个，使用最小堆，我假设构建堆是 O(n)。因为它是一个最小堆，所以较大的元素在后面。然后，弹出后面的元素 'k' 次将花费 k*O(1) = O(k)。因此，复杂度为 O(n + k)。

同样，对于第三个，我假设复杂度也是 O(n + klogn)，这与我对最大堆的推理相同。

但是，一些消息来源仍然说这个问题不能比 heaps/pqs 的 O(n + klogn) 更快！然而，在我的第一个例子中，我认为这个复杂度是 O(n + k)。如果我错了纠正我。需要帮助谢谢。

Answer 1

正确实现，从最小堆中获取第 k 个最大元素是 O((n-k) * log(n))。从最大堆中获取第 k 个最大的元素是 O(k * log(n)).

您的第一个实现完全不正确。例如，如果你想从堆中获取最大的元素（k == 1），循环体将永远不会被执行。您的代码假定向量中的最后一个元素是堆中最大的元素。那是不正确的。例如，考虑堆：

 1
3 2

这是一个完全有效的堆，可以用向量 [1,3,2] 表示。您的第一个实现无法从该堆中获取第一或第二大元素。

第二个解决方案看起来可行。

您的前两个解决方案最终会从 vec 中删除项目。那是你想要的吗？

第三种解法正确。构建堆需要 O(n)，删除最大的 (k-1) 项需要 O((k - 1) log n)。然后 O(1) 访问最大的剩余项。

是另一种方法，在实践中可能更快。思路是：

build a min-heap of size k from the first k elements in vec
for each following element
    if the element is larger than the smallest element on the heap
        remove the smallest element from the heap
        add the new element to the heap
return element at the top of the heap

这是构建初始堆的 O(k)。然后它是 O((n-k) log k) 在最坏的情况下 剩余的项目。最坏的情况发生在初始向量为升序时。这种情况并不经常发生。实际上，一小部分项目会添加到堆中，因此您不必执行所有这些删除和插入操作。

一些堆实现有一个 heap_replace 方法，它结合了删除顶部元素和添加新元素这两个步骤。这降低了一个常数因子的复杂性。（即不是 O(log k) 移除然后 O(log k) 插入，你得到顶部元素的恒定时间替换，然后 O(log k) 将它从堆中筛选出来。

使用堆查找第K大元素的时间复杂度

Time complexity of using heaps to find Kth largest element

c++

heap

search