我们有一个n节点二进制堆,它包含n不同的项(根目录下的最小项).对于a k<=n,找到O(klogk)时间算法以kth从堆中选择最小元素.
O(klogn)显而易见,但无法找出O(klogk)一个.也许我们可以使用第二堆,不确定.
我想提出一些方法来解决以下问题:
给定表示为数组的max-heap,返回第k个最大元素而不修改堆.我被要求在线性时间内完成,但被告知可以在日志时间内完成.
我想到了一个解决方案:
使用第二个最大堆并将其填入k或k + 1值(宽度优先遍历到原始值)然后弹出k个元素并获得所需的值.我想这应该是O(N + logN)= O(N)
是否有更好的解决方案,也许是在O(logN)时间？
这个问题来自采访：
假设第 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个元素出现在两个堆中”？有没有更好的方法利用这些信息？
用于在大小为N的最大堆中找到最大K数的O(K*logK)算法是众所周知的.我听说有一个O(K)算法来解决这个问题.我没有找到关于此的文献.任何人都可以对此提出任何指示吗？谢谢!