我有一个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)
它是否正确？
不，时间比这要好得多。 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)th最小数量的大小。现在，您使用堆是二叉树的事实，并从根开始，并对您找到的小于最大值的每个数字进行递归搜索。然后用k'th最小数字的副本填写列表的其余部分。
在那次搜索中，你将最终看到所有大小相当的k，对于其中一些你会看到最多2个太大而无法打扰的父母，最多的是3k元素。这使整个搜索O(k)。
我怀疑有可能在时间O（k）中识别第k个最小元素 。我以前见过的最好的是O（k log k）算法，它通过识别k个最小元素也可以方便地解决你的问题。您可以在another answer on StackOverflow或Quora上阅读详细信息。
基本思想是操纵二级堆。最初，此辅助堆仅包含原始堆的根。在每个步骤中，算法都会删除辅助堆的min，并将其两个原始子级（即其子级从原始堆）插入到辅助堆中。
该算法具有一个很好的属性，在步骤i中，它从辅助堆中删除的元素是第i个最小元素。因此，在k步之后，已从辅助堆中删除的项集恰好是k个最小元素。该算法是O（k log k），因为在二级堆中存在O（k）删除/插入，其大小上限为O（k）。
编辑：我纠正了！ btilly的答案使用this paper的结果提供了O（k）的解决方案。