how to determine if the kth largest element of the

问题:

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

回答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).

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

use it:

        counter = 0;
        CheckNode(root,index,val,counter );
        if (counter >= index)
            return true;
        return false;

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

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

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.

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

}