4

我知道以前有人问过这个问题。我阅读了以下问题： 如何确定堆的第 k 个最大元素是否大于 x ，但我还有其他问题。我不想在那么旧的线程中发帖。所以：

给定一个 numberx和一个 number k，检查是否x大于 中的k第 -th 最小元素O(k)。

上一个问题做同样的事情，但最大堆和小于。那不是问题。

考虑一个二元最小堆：

              1
      2               3
  12    17         50  90
23,18 80,88      51,52 91,92

让我们x成为 19 岁和k6 岁。

第 6 个最小的元素是 18。

如果我在另一个线程中执行算法，它将检查如下：

1+,2+,12+,23,18+,17+,80,88,3+

+计数器增加时的信号。

算法如何知道 18 是k第一个最小的数字，而不是 3？

为什么 23、80 和 88 的检查不干扰O(k)？

4

1 回答 1

3

算法如何知道 18 是第 k 个最小的数字，而不是 3？

这对算法无关紧要 - 它只是计算较小的数字 - 它不会跟踪哪个是第 k 个最小的数字。

如果它找到多个k较小的数字，它就知道第 k 个最小的数字小于x。

如果我们想真正找到第 k 个最小的数字，我们可能需要做 O(k log k) 的工作，因为我们需要按顺序跟踪候选者，以便我们知道哪一个在第 k 个中位置，或者我们可以做一个（预期的） O(n)快速选择。

为什么13,80,88的检查不会干扰O(k)？

可以这样想——每个节点只有 2 个子节点，如果它小于x，我们只会处理节点的子节点，因此我们可以在的运行时间中包含 和（我们23为涉及和) 和的运行时间。1812122318172

于 2014-06-01T21:05:47.013 回答