使用递归将数组标识为 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) 堆栈 space。如果您有一个非常大的堆（例如，几十万个项目），您运行有溢出堆栈的风险。

一种更常见的递归实现方式是对树进行 depth-first 遍历。也就是说，你一直沿着左边 child 一直到根，然后向上一级检查该节点的右边 child 和它的左边 children 一直到根等等所以，给定这个堆：

          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 来查找 children，我假设您的数组已设置为您的根节点位于索引 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;
}

使用递归将数组标识为 MaxHeap

Using recursion to identify an array as a MaxHeap

java

priority-queue

data-structures

max-heap