相关疑难解决方法(0)

我正在看这个pycon谈话,34:30,发言人说,获取t元素列表中最大的n元素可以完成O(t + n).

怎么可能？我的理解是创建堆将是O(n),但nlargest它本身的复杂性是它O(n + t)还是O(t)(以及实际算法是什么)？

鉴于以下问题,我不能完全确定我目前的解决方案:

题 :

给定n存储在数组中的元素的最大堆A,是否可以打印所有最大的K元素O(K*log(K))？

我的回答:

是的,因为搜索元素需要O(log(K)),因此这样做

为K元素将需要 O(K * log(K))运行时间.

是否有任何关于Frederickson的堆选择算法的简单解释,以便在网上任何地方可用的最小堆中找到O(k)时间中的第k个排序元素？如果没有,任何人都可以解释算法的直觉吗？

这个问题来自采访：

假设第 k 个元素出现在两个堆中，则在 2 个最大堆的并集中查找第 k 个最大元素，时间复杂度为 O(k log n)。

这是我想出的算法：

While k is not zero
 if(root of max-heap #1 > root of max-heap #2)
 {
    extract-max(heap #1)
 }
 else if(root of max-heap #1 < root of max-heap #2)
 {
    extract-max(heap #2)
 }
 else //case of duplicates
 {
    extract-max(heap #1)
    extract-max(heap #2)
 }
 k--

因此，当 k = 0 时，extract-max 函数将提取第 k 大的值。

我认为该算法将在 O(k log n) 时间内运行，因为 extract-max 操作将在 O(log n) 中运行，并且我执行了 k 次。

这是正确的方法吗？看来我没有使用给定的信息“这个第k个元素出现在两个堆中”？有没有更好的方法利用这些信息？