CareerCup

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

htt p : // stackoverflow.com/questions/4922648/how-we-can-find-kth-largest-element-from-a-max-heap-in-ok-time

@topcoder99, Are you missing any data point? Array based heap does not make any difference unless it is a max-heap or a min-heap. Otherwise for a general array, finding the Kth smallest element will itself take O(nlogk) time complexity.

Can someone explain me how finding k smallest element says x is greater than kth smallest element?