考虑一个包含 n 的二叉堆 数字(根存储最大的数字)。你被赋予了 正整数 k < n 和数字 x。你必须确定是否 堆的第 k 个最大元素是否大于 x。你的 算法必须花费 O(k) 时间。你可以使用 O(k) 额外的存储空间
最佳答案
简单的 dfs 就可以完成这项工作。我们有一个计数器设置为零。从根开始，在每次迭代中检查当前节点的值；如果它大于 x，则增加计数器并继续对其中一个子节点执行算法。如果 counter 大于等于 k 或没有节点要检查，则算法终止。运行时间为O(k)，因为最多迭代k个节点，每次迭代时间为O(1)。
伪代码如下所示。
void CheckNode(Node node,int k, int x, ref int counter)
{
if (node.value > x)
{
counter++;
if (counter >= k)
return;
CheckNode(node.Left, k, x, ref counter);
CheckNode(node.Right,k, x, ref counter);
}
}
使用它:
counter = 0;
CheckNode(root,index,val,counter );
if (counter >= index)
return true;
return false;
如果 node.value < x 则所有子值都小于 x 并且不需要检查。
正如@Eric Mickelsen 在评论中提到的，最坏情况下的运行时间正好是 2k-1 (k>0)，如下所示。
The number of nodes visited with values greater than x will be at most k. Each node visited with value less than x must be a child of a visited node with value greater than x. However, because every node visited except the root must have a parent with value greater than x, the number of nodes of value less than x visited must be at most ((k-1)*2)-(k-1) = k-1, since k-1 of the (k-1)*2 children have values greater than x. This means that we visit k nodes greater than x and k-1 less than x, which is 2k-1.
关于algorithm - 如何判断堆的第k大元素是否大于x，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4922648/