heapq库中函数的时间复杂度是多少

Question

我的问题来自下面leetcode中的解决方案，我不明白它为什么是O(k+(n-k)log(k))。

补充：也许复杂性不是那个，实际上我不知道heappush()和heappop()的时间复杂性

# O(k+(n-k)lgk) time, min-heap
def findKthLargest(self, nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
    for _ in xrange(len(nums)-k):
        heapq.heappop(heap)
    return heapq.heappop(heap)

Answer 1

heapq是一个二进制堆，有O（log n）push和O（logn）pop。请参阅heapq source code。

您所展示的算法需要O（n logn）将所有项推送到堆上，然后O（n-k）logn找到第k个最大元素。所以复杂度是O（n logn）。它还需要O（n）额外的空间。

您可以在O（n log k）中执行此操作，只需稍微修改算法，就可以使用O（k）额外空间。我不是Python程序员，所以您必须翻译伪代码：

create a new min-heap
push the first k nums onto the heap
for the rest of the nums:
    if num > heap.peek()
        heap.pop()
        heap.push(num)

// at this point, the k largest items are on the heap.
// The kth largest is the root:

return heap.pop()

这里的关键是堆中只包含迄今为止所看到的最大的项。如果一件东西比目前为止看到的第十大的还小，它就永远不会被堆起来。最坏的情况是O（n log k）。

实际上，heapq有一个heapreplace方法，因此您可以替换它：

    if num > heap.peek()
        heap.pop()
        heap.push(num)

与

    if num > heap.peek()
        heap.replace(num)

另外，推送第一个k项的另一种方法是创建第一个k项的列表并调用heapify。更优化的（但仍然是O（n log k））算法是：

create array of first `k` items
heap = heapify(array)
for remaining nums
    if (num > heap.peek())
        heap.replace(num)
return heap.pop()

您还可以对整个数组调用heapify，然后弹出第一个n-k项，然后进入顶部：

heapify(nums)
for i = 0 to n-k
    heapq.heappop(nums)
return heapq.heappop(nums)

那更简单。不确定它是否比我之前的建议快，但它修改了原始数组。构建堆的复杂性是O（n），然后pops的复杂性是O（（n-k）logn）。所以是O（（n-k）logn）。最坏情况O（n logn）。