java - 我如何检查列表是否是最小二进制堆(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

简答:代码不正确。

您不能从其中一项检查成功的那一刻起简单地返回 true。最小堆是一种结构，其中对于每个节点都必须进行此检查。

此外，检查节点的 parent 是否确实小于(或等于)节点本身更安全。由于堆的最后一层可能不完整。

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++){
        <b>if(x[i] < x[(i-1)/2]){</b> // the node is less than its parent
            return <b>false</b>; // we know there is an error, so return false
        }
   }
   return true; // all checks succeeded, return true
}