递归地检查一个数组是否表示为一个堆。

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

- Hank

---

你真的需要它是递归的吗？ - Denis Tulskiy

看起来没问题。你感觉哪里不对？ - cjds

如果 2i + 1 大于 arr.length，那么 isHeapTree(arr, 2i + 1) 会返回什么... - Hank

不可能像这样不完整，不可以。 - phant0m

Answer 1

一些评论：

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

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

• arr [2 * i + 1] 和 arr [2 * i + 1]可能会引发 ArrayIndexOutOfBoundsException，因此您需要手动进行范围检查或将其包装在 try..catch 块中

- Denis Tulskiy

---

谢谢你的帮助，Denis。我在考虑使用它来检查数组索引，但那可能不是正确的方法。 - Hank

Answer 2

通常情况下，当堆存储在数组中时，它总是向左紧凑排列。换句话说，当堆有n个元素时，索引范围[0，n-1]中的所有数组元素都包含元素。每次插入都从将元素放置在索引size()开始，然后跳到小于其父级的位置。

因此，您采取的方法可以成功。

还要注意，在您的代码中，您可以通过对顶部的保护进行小改变来处理越界问题：

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

private static boolean isHeapTree(int[] arr, int size, int i) {
  assert i >= 0;
  assert size <= arr.length;
  if (i >= size) return true;
  ...

- Dilum Ranatunga