how to determine if the kth largest element of the heap is greater than x

Question

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

Novokuznetsk

-1: it's an interesting problem but this is the wrong way to post a question. Please don't copy an assignment verbatim here. – Unclean

Answer 1

Simple dfs can do the job. We have a counter set to zero. Start from the root and in each iteration check the value of current node; if it is greater than x, then increase the counter and continue the algorithm for one of the child nodes. The algorithm terminates if counter is bigger than equal k or if there is no node left to check. The running time is O(k) because at most k node will be iterated and each iteration is in O(1).

A pseudo-code looks like as 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.

Namangan

"and run algorithm for child nodes" This is the problem. How do you choose, with which child to start? Note, it's not a sorted binary tree, it's only a heap. – Potts

@Saeed No, from which to start. In your code, you're just traversing heap in left-to-right order. But children aren't sorted! node.left may be both less and greater than node.right. There's a picture of binary heap. – Potts

@Nikita Rybak, Children always smaller than their parent, it's not important they are sorted or not, just check them if parent has bigger value, if you are not sure about this simple algorithm add another counter to it, and run it, it will be run at most 3k time. – Namangan

@Saeed Ok, just consider a picture at wikipedia (regardless of x). Your algorithm will declare 19 second greatest value, 17 - third, 2 - forth, 7 - fifth and so on. But we all know it's not so. – Potts

@Nikita Rybak, I'm not finding kth bigger element, Question: "You have to determine whether the kth largest element of the heap is greater than x", if 2k'th largest element is bigger than x, then sure kth largest element is bigger than x. who care about kth largest element? just care about x is greater than that or not. – Namangan

@Nikita Rybak - It doesn't declare which one is kth greatest, only how many elements are greater than x. A heap is sorted in the sense that you only need to consider its children if it is greater than x itself. This algorithm is correct. – Gilberto

@Saeed Ok, apparently I can't read. This is, indeed, correct. Good job. – Potts

@Nikita: Don't beat yourself up. The title is completely misleading. – Donothingism

@Saeed: Thanks for the solution! Anyways, what do you mean by ref counter, and is there any special purpose for using a ref counter instead of a normal int value! – Placable

Couldn't the kth largest element be the right-most leaf of the tree (when k is equal to or greater than the height of the heap), making the worst case performance O(n) or O(2^k), not O(k)? – Frostbitten

@Eric Mickelsen, Question asked for "determine whether the kth largest element of the heap is greater than x or not" not finding Kth largest element , So If you find K items which is bigger than x there is no need to find Kth largest element, In the case which is just smaller than Kth largest element, you know all Parents (in the path from root to Kth largest element) are bigger than this, So maximum height of tree upto Kth Largest element is K, Also you just check child if parent bigger than x(at most K time) so you didn't check more than 3*k node till reaching to Kth largest element. – Namangan

@Saeed Amiri: Thanks, that makes sense. It makes a lot more sense to me to visualize this as finding k elements greater than x - somehow it wasn't clicking for me. Aren't you actually guaranteed to check at most 2*k-1 nodes? – Frostbitten

@Eric Mickelsen, Seems you are right, but currently I thought about it (5 min:) but I see I can't prove it (by elegant way not induction), If you proved it feel free to edit my answer. – Namangan

@Saeed Amiri: 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. – Frostbitten

@EricMickelsen You are right, I'd added your suggested proof. – Namangan

@Saeed Amiri, I just tested your CheckNode solution with the max-heap {11,9,8,6,1,4,3,2) with CheckNode(Node,4,5,ref count) and the pass by reference count variable is incorrect(i.e. 0). Thank you. – Elasmobranch

@Frank, would you say me what was your debug information? Also are you sure you have a maxheap? – Namangan

@Saeed Amiri, Yes, I am sure that {11,9,8,6,1,4,3,2} is a max heap. Also, CheckNode does not have a recursive base case. Finally, are you sure that CheckNode handles the case where x is equal to an max-heap element correctly? Thank you. – Elasmobranch

@Elasmobranch you can see the code, it doesn't check equality so if the element is equal to max heap value it doesn't count it, but yes {11,9,8,6,1,4,3,2} is a max-heap but how do you store it? I mean what is your heap-tree implementation or what's the way of your iteration on array? It's better to post your code. – Namangan

@SaeedAmiri: Great solution, but any insight on why you return at counter >=k rather than counter ==k? – Monthly

@KodeSeeker, because it should be ref counter, and causes to change, I don't know why I changed ref to normal function call. – Namangan

Can someone explain me how finding K items which is bigger than x , says X is greater than Kth largest elem? – Stateroom

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

}

Regulus