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

Question

考虑一个包含n个数字的二进制堆(根存储最大数量).给出正整数k <n和数字x.您必须确定堆的第k个最大元素是否大于x.您的算法必须花费O(k)时间.您可以使用O(k)额外存储空间

Answer 1

简单的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 <x则所有子值都小于x且无需检查.

正如@Eric Mickelsen在评论中提到的,最坏情况下的运行时间恰好是2k-1(k> 0),如下所示.

以大于x的值访问的节点数最多为k.访问的值小于x的每个节点必须是值大于x的受访节点的子节点.但是,因为除root之外访问的每个节点都必须具有值大于x的父节点,所以值小于x的节点数必须最多((k-1)*2) - (k-1)= k -1,因为(k-1)*2个孩子的k-1值大于x.这意味着我们访问大于x的k个节点和小于x的k-1,即2k-1.