在最小堆中，检查 x 是否大于第 k 小的数字。

Question

我知道这个问题之前已经有人问过了。我阅读了以下问题：如何确定堆的第k大元素是否大于x，但是我还有进一步的问题。我不想在旧帖子中发帖，所以：

给定一个数字x和一个数字k，检查x是否比O(k)中第k小的元素大。

之前的问题做了同样的事情，但是使用了最大堆和小于符号。这不是问题所在。

考虑一个二叉小根堆：

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

令x为19，k为6。

第6个最小元素是18。

如果我按照另一个线程中的算法进行，会进行如下检查：

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

+符号表示计数器递增。

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

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

- RunOrVeith

Answer 1

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

对于算法来说这并不重要——它只是计算较小的数字数量——它不会跟踪哪一个是第k个最小的数字。

如果它发现比k更多的较小数字，它就知道第k个最小的数字比x小。

---

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

“那么为什么检查13、80、88不会干扰O(k)呢？”

这样想-每个节点只有2个子节点，只有当它小于x时，我们才会处理节点的子节点，因此我们可以将23和18包含在12的运行时间内(我们对12做了恒定量的工作，包括23和18所涉及的工作)，并将17包含在2的运行时间内。

- Bernhard Barker