0

この Priority Queue の実装では、再帰を使用して、メソッドのパラメーターとして受け取る配列が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 レベル上に移動して、そのノードの右の子、およびその左の子をルートまでずっとチェックします。

          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子を見つけるためにandを使用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 に答える