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

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

14 голосов
/ 07 февраля 2011

Рассмотрим двоичную кучу, содержащую n числа (корень хранит наибольшее число). Вам дают положительное целое число k

Ответы [ 2 ]

24 голосов
/ 07 февраля 2011

Простые 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

Как @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.

0 голосов
/ 06 июня 2016 
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));
}

}

...