1

したがって、これは、配列の特定のインデックスがヒープの最大レベルまたは最小レベルを表すかどうかを判断するために作成したメソッドです。最小レベルの深さは偶数（0を含む）、最大レベルの深さは奇数です。正常に動作しますが、実行時間は（私が思うに）O（log N）です。実行時間が一定である単純な数学計算のように、これを行うためのより効率的な方法はありますか？このメソッドは、データがインデックス0ではなく配列のインデックス1から始まることを前提としていることに注意してください。

    private boolean isMaxLevel(int i)
    {
    int border = 1;
    int prev = 1;
    int count = 1;
    boolean isMax = false;
    // alternates boolean between true and false as each level is checked.
    while (true)
        {
        if (i >= prev && i <= border)
            return isMax;
        isMax = !isMax;
        prev = border + 1;
        count *= 2;
        border += count;
    }
}
4

3 に答える 3

1

あなたの要件が何であるかは私にはわかりませんが、これはあなたを助けるかもしれません.

public static void main(String... args) {
    for (int i = 1; i <= 256; i *= 2) {
        System.out.println((i - 1) + ": " + isOddHighestBit(i - 1));
        System.out.println(i + ": " + isOddHighestBit(i));
    }
}

public static boolean isOddHighestBit(int i) {
    return (Double.doubleToRawLongBits(i) >> 52) % 2 == 0;
}

版画

0: true
1: false
1: false
2: true
3: true
4: false
7: false
8: true
15: true
16: false
31: false
32: true
63: true
64: false
127: false
128: true
255: true
256: false
于 2011-07-22T21:25:03.910 に答える
0

これがより速いかどうかはわかりませんが、おそらく実装に依存しますが、

private boolean isMaxLevel(int i){
    if(((int)Math.log(i+1)/Math.log(2)))%2 == 1)
        return true;
    return false;
}

正しい値を返します。数学的に考えてみてください。i について次のことが当てはまる n を見つけたいとします。n が奇数の場合は最大レベル、n が偶数の場合は最小レベルです。

2ⁿ-1 <= i < 2ⁿ⁺ⁱ-1

これを n について解くと、次のようになります。

2ⁿ-1 <= i < 2ⁿ⁺ⁱ-1
2ⁿ <= i+1 < 2ⁿ⁺ⁱ
n <= log₂(i+1) < n+1
n = floor(log₂(i+1))

次に、n が奇数かどうかをテストできます (n%2 == 1)

于 2011-07-22T21:26:33.290 に答える