Java：检查数组是否为堆

Question

我正在尝试实现检查给定数组是否为堆。

public static boolean Heap(int[] A)

{

    for (int i = 1; i <= (A.length - 2) / 2; i++) {

        if (A[i] < A[2 * i] || A[i] < A[2 * i + 1]) {

            return false;

        }

    }

    return true;

}

A = {50, 45, 40, 35, 20, 25, 20};

B = {45, 50, 40, 35, 20, 25, 20};

    if (Heap(A)) {

        System.out.println("Heap");

    } else {

        System.out.println("Not a heap");

    }

当我为上面的数组调用函数时，它们都返回 true，而 B 应该在 if (A[i] < A[2 * i]...

我究竟做错了什么？

Answer 1

自底向上的解决方案很简单：检查每个节点以查看它是否不大于其父节点。对于最小堆，更改>为<：for (int i = a.length-1; i > 0; --i){&nbsp; &nbsp; int parent = (i-1)/2;&nbsp; &nbsp; if (a[i] > a[parent]) return false;}return true;你会经常看到递归解决方案：bool isMaxHeap(int[] a){&nbsp; &nbsp; return isMaxHeap(a, 0);}bool isMaxHeap(int[] a, int ix){&nbsp; &nbsp; int leftChild = (ix*2)+1;&nbsp; &nbsp; if (leftChild < a.length)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if (a[leftChild] > a[ix]) return false;&nbsp; &nbsp; &nbsp; &nbsp; if (!isMaxHeap(a, leftChild) return false;&nbsp; &nbsp; }&nbsp; &nbsp; int rightChild = leftChild+1;&nbsp; &nbsp; if (rightChild < a.length)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if (a[rightChild] > a[ix]) return false;&nbsp; &nbsp; &nbsp; &nbsp; if (!isMaxHeap(a, rightChild) return false;&nbsp; &nbsp; }&nbsp; &nbsp; return true;}这里的想法是在一个堆中，每个子树也是一个堆。所以我们检查顶层，然后检查树的每个分支。我们递归地应用它。

Answer 2

也许这就是你想要的：public static void main(String... args) {&nbsp; &nbsp; int[] A = {50, 45, 40, 35, 20, 25, 20};&nbsp; &nbsp; int[] B = {45, 50, 40, 35, 20, 25, 20};&nbsp; &nbsp; System.out.println(isMaxHeap(A));&nbsp; &nbsp; System.out.println(isMaxHeap(B));}private static boolean isMaxHeap(int[] arr) {&nbsp; &nbsp; int N = arr.length;&nbsp; &nbsp; for (int i = (N - 2) / 2; i > -1; --i) { // start from the first internal node who has children;&nbsp; &nbsp; &nbsp; &nbsp; int j = 2 * i + 1; // the left child;&nbsp; &nbsp; &nbsp; &nbsp; if (j < N - 1 && arr[i] < arr[j+1]) j++; // select the bigger child;&nbsp; &nbsp; &nbsp; &nbsp; if (arr[i] < arr[j]) return false; // if parent is smaller than the child;&nbsp; &nbsp; }&nbsp; &nbsp; return true;}但是请在下次询问之前表现出一些努力。