algorithm - 如何确定堆的第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 的已访问节点的子节点。但是，因为除了根节点之外，每个访问的节点都必须有一个值大于 x 的父节点，所以访问的值小于 x 的节点的数量最多只能是 ((k-1)*2)-(k-1) = k -1，因为 (k-1)*2 个孩子中的 k-1 个具有大于 x 的值。这意味着我们访问了大于 x 的 k 个节点和小于 x 的 k-1 个节点，即 2k-1。

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));
}

}