我们如何递归地检查数组是否表示堆数据结构? 假设它是一个整数数组,我正在检查最大堆。 以下是我想出的,但我不知道这是否正确。
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
最佳答案
一些评论:
您绝对不需要 while 循环 - 您总是在第一次迭代后返回
2i + 1
在 java 中不起作用,你需要使用2*i + 1
arr[2*i + 1]
和arr[2*i + 1]
可能抛出和ArrayIndexOutOfBoundsException
所以你需要手动进行范围检查,或将其包装在try..catch
block 中
关于java - 递归检查数组是否代表堆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13852854/