3

配列がヒープデータ構造を再帰的に表しているかどうかを確認するにはどうすればよいですか? それが整数の配列であると仮定し、最大ヒープをチェックしています。以下は私が思いついたものですが、それが正しいかどうかはわかりません。

public static boolean isHeap(int[] arr) {
      if (arr = null)
           return false;
      return isHeapTree(arr, 0);
}

private static boolean isHeapTree(int[] arr, int i) {
           if (i = arr.length - 1)
               return true;
           // check if a parent's value is larger or equal to both of
           // its left child and right child
           else if (arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2])
               return (isHeapTree(arr, 2i + 1) && isHeapTree(arr, 2i + 2));
           else
               return false;
}

is it possible a binary heap could be incomplete? say:
         100
        /   \
       50   20
      /  \    \
     30  40   26
4

2 に答える 2

2

いくつかのコメント:

  • whileループは絶対に必要ありません-最初の反復の後に常に戻ります

  • 2i + 1Javaでは動作しません。使用する必要があります2*i + 1

  • arr[2*i + 1]arr[2*i + 1]スローされる可能性がArrayIndexOutOfBoundsExceptionあるため、手動で範囲チェックを行うか、try.. catchブロックでラップする必要があります

于 2012-12-13T04:29:23.040 に答える
1

通常、ヒープが配列に格納される場合、ヒープは常に左側にパックされます。つまり、ヒープにn要素がある場合、インデックス範囲内の配列内のすべての要素に要素が[0, n-1]含まれます。すべての挿入は、要素をインデックスsize()に配置することから始まり、次に、親よりも小さくなるまでジャンプします。

したがって、あなたが取っているアプローチは成功することができます。

また、コードでは、ガードを少し変更するだけで範囲外に対処できることに注意してください。

public static boolean isHeap(int[] arr, int size) {
  return (null == arr) ? false : isHeapTree(arr, size, 0);
}

private static boolean isHeapTree(int[] arr, int size, int i) {
  assert i >= 0;
  assert size <= arr.length;
  if (i >= size) return true;
  ...
于 2012-12-13T05:10:23.920 に答える