Какова временная сложность функций в библиотеке heapq? ⇐ Python

[Anonymous]

Мой вопрос связан с решением в коде ниже, я не могу понять, почему это 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)


Подробнее здесь: https://stackoverflow.com/questions/388 ... pq-library