algorithm - 如何确定堆的第k个最大元素是否大于x

考虑一个包含n的二进制堆
数字（根存储最大的数字）给你一个
正整数k堆的第k个最大元素是否大于x你的
算法必须花费O（k）时间您可以使用额外的存储空间

最佳答案

简单的dfs可以完成这项工作我们把计数器设为零从根节点开始，在每次迭代中检查当前节点的值；如果该值大于x，则增加计数器并继续对其中一个子节点执行算法如果计数器大于等于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正如@Eric Mickelsen在评论中提到的，最坏情况下运行时间正好是2k-1（k>0），如下所示。
值大于x的访问节点数最多为
k.访问的每个值小于x的节点必须是
值大于x的已访问节点。但是，因为每个节点
已访问，但根目录必须具有值大于x的父目录，
访问的值小于x的节点数必须最多为
（（k-1）*2）-（k-1）=k-1，因为（k-1）*2个孩子的k-1有值
大于x。这意味着我们访问大于x的k个节点
k-1小于x，即2k-1。

关于algorithm - 如何确定堆的第k个最大元素是否大于x，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13719966/