查找min-heap是否具有比query小的k个元素

Question

我想了很长时间都在挠头。我需要找到一个O(k)算法来确定最小堆中是否有比查询q更小的k元素。

我尝试过这样的递归算法：

count = 0;
def kSmaller(H, q, k){
   if (root(H) == Null or root(H) >= q ) return;
   else {count++;
         if (count == k) return true;
         kSmaller(LeftChild(root(H), q, k)
         kSmaller(RightChild(root(H), q, k)
    }
}

但是在看了一些最小堆的例子之后，我不太理解如何在O(k)时间内终止，而不是不必要地遍历每个元素。

有没有人能帮我理解一下该怎么做呢？也许最好不要使用递归，而是将解决方案扁平化。

Answer 1

Min堆的排列方式是每个节点都小于它的两个子树中的所有节点。因此，当您看到一个大于或等于Q值的节点时，您的代码将花费O(k)时间，因为您将删除递归。你可以画几个例子，看看。如果Min堆有小于q的p个节点，那么你只需要min(p，k)时间，你能看到吗？

Answer 2

这个算法实际上是O(k)时间的另一种方法是这样的：

让所有节点最初都是白色的。如果节点被递增count的kSmaller()调用访问，则将其显示为黑色；如果未递增count的调用访问该节点，则将其显示为灰色。当count没有递增时，递归会暂停，因此灰色节点下的每个节点都必须是白色的；哦，黑色节点的每个子节点必须是黑色或灰色的。显然，确实存在count黑色节点，并且由于每个节点最多有2个子节点，因此最多可以有count * 2灰色节点，因此总体上最多可以有count * 3访问(即黑色或灰色)节点。由于count显然始终保持<= k，因此访问的节点不超过3k。最后，由于每次调用只完成O(1)项工作(不包括在递归调用中花费的时间)，因此总体时间复杂度最差为O(k)。