在最小堆中获取前 n 个最大元素的时间复杂度是多少？

Question

鉴于python中的heapq是python doc中指定的最小堆，假设我有一个包含m个元素的heapq，调用nlargest的时间复杂度是多少？我不认为复杂性是 O(n*lg(m)) 因为简单地弹出根并在最小堆中再次堆化只会让你最小？

heapq.nlargest 是如何工作的？

Answer 1

您可以在此处查看代码。假设您执行 a heapq.nlargest(n, it)， whereit是带有m元素的可迭代对象。它首先用 的第一个n元素构造一个最小堆it。然后，对于其余m-n元素，如果它们大于根，则取出根，放入新元素，并将其向下移动。最后，复杂度为O(log(n) * m)。