Как я могу проверить, является ли список минимальной двоичной кучи (Java)?

Question

Здравствуйте, мне нужна помощь для моей домашней работы. Как я могу проверить, является ли список минимальной двоичной кучей? Пожалуйста, скажите мне, если я сделал это правильно:

public boolean check(int [] arr){
  if(arr[0]==null){
    return false;
  }
  for(int i=0 ; i<arr.length ;i++){
    if(x[i]<x[2i+1] && x[i]<x[2i+2]){
      return true;
    }
   return false;
}

Answer 1

Краткий ответ: код неверный.

Вы не можете просто return true с момента успешного прохождения одной из проверок. Minheap - это структура, в которой для каждого узла должна выполняться эта проверка.

Кроме того, более безопасно проверять, является ли родительский узел независимым меньше (или равен) самого узла. Так как последний слой кучи может быть неполным.

public boolean check(int [] arr){
    if(arr == null){ // check whether the arr is null itself, not the element
        return false; // here we assume null is not a heap (open for discussion)
    }
    for(int i=1 ; i < arr.length ;i++){
        if(x[i] < x[(i-1)/2]){ // the node is less than its parent
            return false; // we know there is an error, so return false
        }
   }
   return true; // all checks succeeded, return true
}

Answer 2

У тебя все наоборот.

Вам нужно, чтобы ВСЕ элементы соответствовали критериям, а ваш код проверяет, соответствует ли ЛЮБОЙ элемент критериям.

Вам следует return false в случае нарушения этого критерия, и если вы сделали, не найдя ни одного - return true,
Также: не забудьте убедиться, что у вас нет доступа x[2*i+1] когда i > x.length()/2

public boolean check(int [] arr){
  if(arr==null){
    return false;
  }
  for(int i=0 ; i<arr.length ;i++){
    // check if the min heap property is violated
    if((2*i + 1 < arr.length && x[i] > x[2*i+1]) || (2*i + 2 < arr.length && x[i]>x[2i+2])){
      return false;
    }
  }
  return true;
}