相关疑难解决方法(0)

我想提出一些方法来解决以下问题:

给定表示为数组的max-heap,返回第k个最大元素而不修改堆.我被要求在线性时间内完成,但被告知可以在日志时间内完成.

我想到了一个解决方案:

使用第二个最大堆并将其填入k或k + 1值(宽度优先遍历到原始值)然后弹出k个元素并获得所需的值.我想这应该是O(N + logN)= O(N)

是否有更好的解决方案,也许是在O(logN)时间？

考虑一个包含n个数字的二进制堆(根存储最大数量).给出正整数k <n和数字x.您必须确定堆的第k个最大元素是否大于x.您的算法必须花费O(k)时间.您可以使用O(k)额外存储空间

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

题 :

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

我的回答:

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

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

我正在寻找一种在二进制堆（最大或最小）上实现迭代器的方法。

也就是说，通过第i次使用其nextNode（）函数，可以获得堆中第i个（更大或更小的）元素。

请注意，此操作是在没有实际提取堆根的情况下发生的！

我最初的想法是：

• 实际上提取i元素，将它们压入堆栈，然后在获得第i个值后将它们重新插入堆中。每个函数调用都需要O（i * log（n））。
• 保留一个辅助排序的数据结构，该结构可以允许在O（1）中查找下一个值，但是更新将占用O（n）。

我了解这些方法消除了使用堆的好处，因此我正在寻找一种更好的方法。

我有一个包含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)

这样对吗？