java - 最小ヒープで最大値を見つける

Question

私は試験のために勉強していました、そして私が見ていましたワークシートの1つから、それは整数を格納する最小ヒープのためのメソッドlargest（）を書くように頼みます。

public class Heap {
   private int[] arr = new int[100];
   private int numElts = 0;

   public int largest(){

  }

}

最大サイズは100要素であり、newEltはヒープに格納されている要素の現在の数を追跡します。

私は次のようなことを考えていました：

int[] newArr = Collections.sort(arr);
return newArr[newElt];

しかし、それは元のヒープを変更します。ディープコピーを作成することはできますが、ヒープのすべての要素を調べる必要はないと書かれています。

それで、誰もがすべての要素を見ずにこれを行う方法を提案できますか？ありがとう、

score 3 · Accepted Answer

構造がヒープ順の場合、それが -max heap- の場合、最大要素は単純にになりますarr[0]。しかし、これは最小ヒープであるため、最大要素がリーフノードであることがわかっているだけです。

したがって、すべての要素をテストする必要はありません。ただし、要素の最大で半分を確認する必要があります (バイナリツリーの場合、葉の数は 1 からサイズの半分に 1 を加えたもので、両方のアカウントを含めます)。

バイナリヒープ (説明したもの) が特殊なバランスのとれたバイナリツリーであることを知ることで、リーフノードを簡単に調べることができます。これにより、小さな計算で 2 つのリーフノードのセットがどこにあるかがわかります。

1 に答える 1