0 
public BinaryHeap( AnyType [ ] items ) {
    currentSize = items.length;
    array = (AnyType[]) new Comparable[ ( currentSize + 2 ) * 11 / 10 ];

    int i = 1;
    for( AnyType item : items )
        array[ i++ ] = item;
    buildHeap( );
}

なぜarray.length = (currentSize + 2) * 11 /10ですか？

4

1 に答える 1

0

私なら次のように解釈します。

  • currentSize + 2- ヒープにさらに 2 つの要素が追加されることは確実です。容量を 2 つ増やします
  • (currentSize + 2) * 11/10 - 容量を 10% 増やします

問題は、そのようなヒープ実装には容量が制限されていることです-割り当てられた配列の長さによって制限されます。要素を挿入するときは((currentSize + 2) * 11/10 + 1)、配列のサイズを変更する必要がありますが、これはコストのかかる操作になる可能性があります。特に、古い配列の長さを 1 ずつ増やしてサイズを常に変更している場合は特にそうです。

コードの作成者は、配列のサイズが、追加される可能性のあるすべての要素を保持するのに十分であることを確認したかったようです。

編集：

Ivaylo Strandjev がコメントで述べたように、ヒープ サイズを設定する通常の方法は、そのkようなものを選択すること2^k > currentSizeです。入力項目のサイズが十分に大きい場合、コードの作成者はそのアプローチを選択しない可能性があります。

たとえば、ほとんどの場合、予想される入力サイズは最大 1200 で、ピークは 1500 で、最初の入力サイズは 1025 要素です。通常のアプローチでは、k=11 を選択する必要があります -> サイズは 2048 ですが、これは (2048 - 1500 = 548) * メモリ内の AnyType オブジェクト バイトのサイズを浪費することを意味します。

于 2013-03-22T13:57:46.650 に答える