Как определить, является ли k-й наибольший элемент кучи больше x

Ответ 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 из (k-1) * 2 дочерних элементов имеют значения, превышающие x. Это означает, что мы посещаем k узлов больше, чем x, и k-1 меньше, чем x, что составляет 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));
}

}