java - 使用递归将数组识别为 MaxHeap

Question

在优先队列的实现中，我必须使用递归来确定作为方法 IsMaxHeap 的参数接收的数组是否是最大堆。

我想确保我评估了所有可能使这项工作正常进行或不正常工作的情况。

static boolean isMaxHeap(int[] H, int idx) {

    if(2*idx == (H.length -1) && H[2 * idx] <= H[idx])
        return true;
    if(2*idx > (H.length -1))
        return true;
    if ((2*idx+1) == (H.length -1) && H[2 * idx] <= H[idx] && H[2 * idx + 1] <= H[idx])
        return true;
    if((2*idx+1) > (H.length -1))
        return true;

    if (H[2 * idx] <= H[idx] && H[2 * idx + 1] <= H[idx])
        return isMaxHeap(H, (idx + 1));
    else
        return false;

}

你能帮我吗？

Answer 1

你的代码很难理解，因为你在条件中做了很多计算。所以很难说它是否真的有效。另外，您编写的内容基本上是 for 循环的递归实现。也就是说，您检查节点 1、2、3、4、5 等。

尽管这可行，但您最终会使用 O(n) 堆栈空间。如果您有一个非常大的堆(例如，数十万个项目)，则存在堆栈溢出的风险。

一种更常见的递归实现方法是对树进行深度优先遍历。也就是说，您沿着左子节点一直到根，然后上升一级并检查该节点的右子节点及其左子节点一直到根，依此类推。因此，给定这个堆:

          1
    2           3
 4    5      6      7
8 9 10 11  12 13  14 15

您将按以下顺序检查节点:[1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]

这样做可以简化您的代码，并将堆栈深度限制为 O(log n)，这意味着即使有 100 万个节点，您的堆栈深度也不会超过 20。

由于您使用 2*idx 和 2*idx+1 来查找子项，我假设您的数组已设置为您的根节点位于索引 1。如果根位于索引 0，则这些计算将为:2*idx+1 和 2*idx+2。

static boolean isMaxHeap(int[] H, int idx)
{
    // Check for going off the end of the array
    if (idx >= H.length)
    {
        return true;
    }

    // Check the left child.
    int leftChild = 2*idx;
    if (leftChild < H.length)
    {
        if (H[leftChild] > H[idx])
           return false;
        if (!isMaxHeap(H, leftChild)
            return false;
    }

    // Check the right child.
    int rightChild = 2*idx + 1;
    if (rightChild < H.length)
    {
        if (H[rightChild] > H[idx])
            return false;
        return isMaxHeap(H, rightChild);
    }

    return true;
}