algorithm - ヒープの k 番目に大きい要素が x より大きいかどうかを判断する方法

Question

n 個の数値を含むバイナリ ヒープを考えてみましょう (ルートには最大の数値が格納されます)。正の整数 k < n と数値 x が与えられます。ヒープの k 番目に大きい要素が x より大きいかどうかを判断する必要があります。アルゴリズムは O(k) 時間かかる必要があります。O(k) 追加ストレージを使用できます

Answer 1

シンプルな dfs で十分です。ゼロに設定されたカウンターがあります。ルートから開始し、各反復で現在のノードの値を確認します。x より大きい場合は、カウンターを増やして、子ノードの 1 つに対してアルゴリズムを続行します。カウンターが等しい k よりも大きい場合、またはチェックするノードが残っていない場合、アルゴリズムは終了します。最大 k ノードが反復され、各反復が O(1) であるため、実行時間は O(k) です。

擬似コードは次のようになります。

    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 Mikelsen がコメントで述べたように、最悪の場合の実行時間は次のように正確に 2k-1 (k>0) です。

x より大きい値で訪問されたノードの数は、最大で k になります。x より小さい値で訪問された各ノードは、x より大きい値で訪問されたノードの子でなければなりません。ただし、ルートを除くアクセスされるすべてのノードには x より大きい値を持つ親が必要であるため、アクセスされる x より小さい値のノードの数は最大で ((k-1)*2)-(k-1) = k でなければなりません。 -1 ((k-1)*2 の子の k-1 が x より大きい値を持っているため)。これは、x より大きく、x より k-1 小さいノード (2k-1) の k 個のノードにアクセスすることを意味します。

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

}