在最小堆中找到 k 个最小元素 - 最坏情况的复杂性

Question

我有一个包含n元素的最小堆，并想k从这个堆中找到最小的数字。最坏情况的复杂度是多少？

这是我的方法：在 stackoverflow 的某个地方，我读到在最小堆中找到第 i 个最小数字的复杂性是O(i)。因此，如果我们想找到n-1最小的数字（n 毫无意义，因为它将是整个堆），总复杂度将如下所示：

O(n-1)+O(n-2)+O(n-3)+…+O(2)+O(1)=O((1+n-1)*(n/2))=O(n^2)

这样对吗？

Answer 1

不，时间比那要好得多。 O(k log(n))很容易，O(k)如果你很聪明。

从堆中查找并删除最小元素是O(log(n))。这O(k log(n))很容易导致时间。

但结果是你想的是https://ac.els-cdn.com/S0890540183710308/1-s2.0-S0890540183710308-main.pdf?_tid=382a1cac-e4f7-11e7-8ac9-00000aab0f02&acdnat=1513713791_08f4df78a8821855e8ec788da063ea2f昭示着如何找到k时间中最小的数字的大小O(k)。现在，您使用堆是二叉树这一事实，并从根开始递归搜索您找到的每个小于最大数字的数字。然后用k“最小的数字”的副本填写列表的其余部分。

在该搜索中，您最多会看到k-1最多那个大小的东西，对于其中一些，您最多会看到 2 个太大而无法打扰的子3k-3元素，最多元素。这使得整个算法O(k)。