扬声器在这种情况下是错误的。实际费用为O(n * log(t))。仅在titerable 的第一个元素上调用Heapify
。就是那个O(t)，但如果t小于，则微不足道n。然后，将所有剩余的元素一次通过添加到此“小堆”中heappushpop。O(log(t))每次调用需要花费时间heappushpop。堆的长度始终保持不变t。最后，对堆进行了排序，这很费钱O(t * log(t))，但是如果堆t大小小于，那么这也是无关紧要的n。

理论上的乐趣;-)

有相当容易的方法可以在预期的O(n)时间内找到第t个最大元素。例如，请参阅此处。在最坏的情况下，有更困难的方法可以做到这一点O(n)。然后，在另一遍输入上，您可以输出t>
=第t个最大元素（如果有重复，则繁琐繁琐）。因此，整个工作 可以 及时完成O(n)。

但是这些方式也需要O(n)内存。Python不使用它们。实际实现的优点是，最坏情况下的“额外”内存负担为O(t)，当输入是例如产生大量值的生成器时，这可能非常重要。