我知道这个问题以前曾被问过。我读了以下问题：如何确定堆的第k个最大元素是否大于x，但还有其他问题。我不想在这么老的帖子中发帖。所以：
给定一个数字x和一个数字k，检查是否x大于中的k-th个最小元素O(k)。
前面的问题做同样的事情，但最大堆数小于。那不是问题。
考虑二进制最小堆：
1
2 3
12 17 50 90
23,18 80,88 51,52 91,92
设x19和k6。
第六小的元素是18。
如果我在另一个线程中执行该算法，它将进行如下检查：
1+,2+,12+,23,18+,17+,80,88,3+
该+信号时，计数器增加。
算法如何知道18是k最小的-个数字，而不是3？
为什么23、80和88的检查不干扰O(k)？
该算法如何知道18是第k个最小数字，而不是3？
该算法无关紧要-它只计算较小的数字-它无法跟踪哪个是第k个最小数字。
如果发现的k数目多于较小的数目，则知道第k个最小数目小于x。
如果我们想真正找到第k个最小的数，我们可能需要做O（k log k）个工作，因为我们需要按顺序跟踪候选者，以便我们知道第k个是哪个位置，否则我们可以执行（预期）O（n）quickselect。
为什么13,80,88的支票不干扰O（k）？
可以这样考虑-每个节点只有2个子节点，并且如果节点的子节点小于，我们将只处理它的子节点x，因此我们可以在23和的运行时间内包含和（我们为进行了固定数量的工作，包括对于参与和），并在的运行时间。1812122318172
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句