0

在优先队列的这个实现中，我必须使用递归来确定我作为方法参数接收的数组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;

}

你可以帮帮我吗？

4

1 回答 1

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)，这意味着即使有一百万个节点，您的堆栈深度也不会超过 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;
}
于 2016-01-07T14:34:44.443 回答