algorithm - 在 O(K*log(K)) 中打印给定堆中最大的 K 个元素？

Question

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

问题:

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

我的回答:

是的，是的，因为搜索一个元素需要 O(log(K)) ，所以这样做

K 元素需要 O(K * log(K)) 运行时间。

Answer 1

在大小为 N 的堆中搜索元素不是 O(K)。首先，查找 一个 元素的时间复杂度取决于您尝试提取的元素数量(这是 K 代表的)是没有意义的。此外，不存在在堆中进行搜索这样的事情——除非您计算 O(N) 中标准的查看每个元素的搜索。

然而，在堆中找到最大元素的设计复杂度为 O(1)(我显然假设它是一个最大堆，因此最大元素位于堆的顶部)，并从中移除最大元素大小为 N 的堆的复杂度为 O(log(N))(将其替换为叶元素，并让该叶元素向下渗透到堆中)。

因此，从堆中提取 K 个元素，并返回未提取元素的堆，将花费 O(K·log(N)) 时间。

如果您非破坏性地从堆中提取 K 个元素会怎样？您可以通过保留堆堆(其中堆的值是其最大元素的值)来做到这一点。最初，这个堆堆只包含一个元素(原始堆)。要提取下一个最大元素，您可以提取顶堆，提取其顶部元素(即最大值)，然后将两个子堆重新插入堆中。

这会使堆中的堆在每次移除时增加一个(移除一个，添加两个)，这意味着它永远不会容纳超过 K 个元素，因此移除一个添加-two 将占用 O(log(K))。对此进行迭代，您会得到一个实际的 O(K·log(K)) 算法，该算法确实返回前 K 个元素，但无法返回未提取元素的堆。