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

Question

考虑一个包含n个数字的二叉堆（根节点存储最大数）。给定正整数k < n和一个数x。您需要确定堆的第k个最大元素是否大于x。您的算法必须在O(k)时间内完成。您可以使用额外O(k)的存储空间。

- Prajapat

---

-1：这是一个有趣的问题，但这不是正确的提问方式。请不要直接复制作业到这里。 - Jason S

Answer 1

简单的深度优先搜索可以完成该任务。我们将计数器设置为零，从根节点开始，每一次迭代检查当前节点的值；如果大于 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;

如果节点的值小于x，则所有子节点的值都小于x，无需检查。

正如@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。这意味着我们访问k个大于x的节点和k-1个小于x的节点，总共访问了2k-1个节点。

- Saeed Amiri

---

@Nikita Rybak，我没有找到第k大的元素。问题是：“您必须确定堆中第k个最大元素是否大于x”，如果第2k大的元素比x大，那么第k大的元素肯定也比x大。谁关心第k大的元素？只需要关心x是否大于它就可以了。 - Saeed Amiri

@Saeed 好的，显然我没看清。这是正确的。干得好。 - Nikita Rybak

@Nikita：不要自责。标题完全误导了。 - Aryabhatta

@Eric Mickelsen，问题是“确定堆的第k大元素是否大于x”，而不是找到第k大的元素。因此，如果你找到了K个大于x的元素，就没有必要找第k大的元素了。在只比第k大元素小的情况下，你知道所有父节点（从根到第k大元素的路径）都比它大。所以，最高的树高度到第k大元素为K。另外，你只需要检查父节点是否大于x的子节点（最多K次），这样在达到第k大元素之前，你最多检查不超过3*k个节点。 - Saeed Amiri

@Saeed Amiri：访问值大于x的节点数最多为k。每个访问的值小于x的节点必须是一个具有大于x值的已访问节点的子节点。然而，由于除根节点外的每个访问节点都必须具有大于x的父节点，因此访问的值小于x的节点数必须最多为((k-1)*2)-(k-1)=k-1，因为(k-1)*2个子节点中有k-1个具有大于x的值。这意味着我们访问了k个大于x的节点和k-1个小于x的节点，总共为2k-1个节点。 - Eric Mickelsen

Answer 2

public class KSmallest2 {

private MinPQ<Integer> minHeap;
private int x;
private int k;
private int count = 0;

public KSmallest2(String filename, int x, int k) {
    this.x = x;
    this.k = k;
    minHeap = new MinPQ<>();
    try {
        Scanner in = new Scanner(new File(filename));
        while (in.hasNext()) {
            minHeap.insert(in.nextInt());
        }
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
}

public boolean check(int index) {

    if (index > minHeap.size()) {
        return false;
    }

    if (minHeap.getByIndex(index) < x) {
        count++;
        if (count >= k) {
            return true;
        }

        return  check(2 * index) ||
                check(2 * index + 1);
    }

    return false;
}



public static void main(String[] args) {
    KSmallest2 ks = new KSmallest2("src/main/resources/minheap.txt", 18, 5);
    System.out.println(ks.minHeap);

    System.out.println(ks.check(1));
}

}

- irudyak