algorithm - 如何判断堆的第k大元素是否大于x

Question

考虑一个包含 n 的二叉堆数字(根存储最大的数字)。你被赋予了正整数 k < n 和数字 x。你必须确定是否堆的第 k 个最大元素是否大于 x。你的算法必须花费 O(k) 时间。你可以使用 O(k) 额外的存储空间

Answer 1

简单的 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.