java - 递归检查数组是否代表堆

Question

我们如何递归地检查数组是否表示堆数据结构？假设它是一个整数数组，我正在检查最大堆。以下是我想出的，但我不知道这是否正确。

public static boolean isHeap(int[] arr) {
      if (arr = null)
           return false;
      return isHeapTree(arr, 0);
}

private static boolean isHeapTree(int[] arr, int i) {
           if (i = arr.length - 1)
               return true;
           // check if a parent's value is larger or equal to both of
           // its left child and right child
           else if (arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2])
               return (isHeapTree(arr, 2i + 1) && isHeapTree(arr, 2i + 2));
           else
               return false;
}

is it possible a binary heap could be incomplete? say:
         100
        /   \
       50   20
      /  \    \
     30  40   26

Answer 1

一些评论:

• 您绝对不需要 while 循环 - 您总是在第一次迭代后返回

• 2i + 1 在 java 中不起作用，你需要使用 2*i + 1

• arr[2*i + 1] 和 arr[2*i + 1] 可能抛出和 ArrayIndexOutOfBoundsException 所以你需要手动进行范围检查，或将其包装在 try..catch block 中