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)

{

    int parent = (i-1)/2;

    if (a[i] > a[parent]) return false;

}

return true;

你会经常看到递归解决方案：

bool isMaxHeap(int[] a)

{

    return isMaxHeap(a, 0);

}

bool isMaxHeap(int[] a, int ix)

{

    int leftChild = (ix*2)+1;

    if (leftChild < a.length)

    {

        if (a[leftChild] > a[ix]) return false;

        if (!isMaxHeap(a, leftChild) return false;

    }

    int rightChild = leftChild+1;

    if (rightChild < a.length)

    {

        if (a[rightChild] > a[ix]) return false;

        if (!isMaxHeap(a, rightChild) return false;

    }

    return true;

}

这里的想法是在一个堆中，每个子树也是一个堆。所以我们检查顶层，然后检查树的每个分支。我们递归地应用它。

Answer 2

也许这就是你想要的：

public static void main(String... args) {

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

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

    System.out.println(isMaxHeap(A));

    System.out.println(isMaxHeap(B));

}

private static boolean isMaxHeap(int[] arr) {

    int N = arr.length;

    for (int i = (N - 2) / 2; i > -1; --i) { // start from the first internal node who has children;

        int j = 2 * i + 1; // the left child;

        if (j < N - 1 && arr[i] < arr[j+1]) j++; // select the bigger child;

        if (arr[i] < arr[j]) return false; // if parent is smaller than the child;

    }

    return true;

}

但是请在下次询问之前表现出一些努力。