algorithm - 查找最小堆是否有 k 个小于查询的元素

Question

我一直在挠头思考这个问题。我需要找到一个 O(k) 算法来确定最小堆是否有 k 个小于查询 q 的元素。

我试过这样的递归算法:

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

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