如何确定是否堆的第k个最大元素是比x大 [英] how to determine if the kth largest element of the heap is greater than x

问题描述

考虑一个二进制含堆ñ 数（根存储的最大数）。您将得到一个 正整数k＆其中; n和一个数x。你必须决定是否 堆的第k个最大元素大于x或不。您的 算法必须采取O（k）的时间。您可以使用O（k）的额外的存储空间

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x. You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage

推荐答案

简单的DFS可以做到这一点，我们有一个计数器设置为零。开始从根和在每次迭代检查节点值，如果大于x，则增加计数器和运行算法为子节点。当计数器是更大或等于k的算法将完成，也如果没有节点检查，算法返回false。在code是简单的。运行时间为O（K），因为顶多你会检查的K节点，每个迭代是O（1）。

Simple dfs can do it, we have a counter set to zero. Start from the root and in each iteration check the node value if is greater than x, then increase the counter and run algorithm for child nodes. When the counter is bigger or equal to k the algorithm will be finished, also if there is no node to check, algorithm returns false. The code is simple. The running time is O(k) because at most you will check k node and each iteration is O(1).

伪code看起来如下：

The pseudo-code looks like follows.

    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＆LT; x然后所有儿童值小于x，没有必要检查

if node.value < x then all children values are smaller than x and there is no need to check.

由于@Eric Mickelsen在评论中提到最坏情况下的运行时间恰好是2K-1（K> 0）如下：

As @Eric Mickelsen mentioned in comments worst case running time is exactly 2k-1 (k>0) as follows.

节点的数量走访值大于x将至多   ķ。参观了值小于x的每个节点必须是一个孩子   访问节点的值比x大。然而，因为每一个节点   访问了除了根必须有一个父与值大于X，   的值小于x个节点的被访问的次数必须至多   （（K-1）* 2） - （K-1）= k-1个，由于k-1第（k-1）的* 2个孩子具有值   大于x。这意味着，我们参观ķ比x个节点更大，   K-1小于x​​，它为2k-1

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.

这篇关于如何确定是否堆的第k个最大元素是比x大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！