Проверка четно-нечетных уровней кучи min-max java - PullRequest
Новая
       31

Проверка четно-нечетных уровней кучи min-max java

1 голос
/ 23 июля 2011

Так что это метод, который я написал, чтобы определить, представляет ли данный индекс массива максимальный уровень или минимальный уровень кучи, где минимальный уровень имеет четную глубину (включая 0), максимальный уровень имеет нечетную глубину.Он работает нормально, но его время выполнения (я думаю) O (журнал N).Есть ли более эффективный способ сделать это, как простой математический расчет с постоянным временем выполнения?Обратите внимание, что этот метод предполагает, что данные начинаются с индекса 1 массива, а не индекса 0. 

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

Ответы [ 3 ]

1 голос
/ 23 июля 2011

Мне не ясно, каковы ваши требования, но это может помочь вам. 

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
0 голосов
/ 28 мая 2013

мы должны определить минимальный и максимальный уровни

1 => pow (2,0) -> минимальный уровень

2-3 => pow (2,1) to pow (2,2) -1 -> максимальный уровень

4-7 => от Pow (2,2) до Pow (2,3) -1 -> минимальный уровень

8-15 => pow (2,3) to pow (2,4) -1 -> максимальный уровень

c реализация 

#include<math.h>
#define bool int
#define true 1
#define false 0
int isMinLevel(int i,int n)//i is on min level or not
{
  int h=2;
  if(i==1)
    return true;
  while(true)
    {
      if(i>=pow(2,h)&&i<=pow(2,h+1)-1)
    return true;
      else if(i>n||i<pow(2,h))
    return false;
      h+=2;
    }
}
0 голосов
/ 23 июля 2011

Я не уверен, что это быстрее, возможно, это зависит от реализации, но: 

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

Возвращает правильное значение.Думайте об этом математически.Вы хотите выяснить, для чего 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)

...