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- 肯定会有两个元素添加到堆中，将容量增加两个
  • (currentSize + 2) * 11/10 - 容量增加 10%

问题是，这种堆实现的容量有限——受分配数组长度的限制。插入((currentSize + 2) * 11/10 + 1)元素时，您需要调整数组的大小，这可能是一项代价高昂的操作。特别是如果您总是通过将旧数组长度增加一来调整大小。

看起来代码的作者想要确保数组的大小足以容纳可能添加到其中的所有元素。

编辑：

正如 Ivaylo Strandjev 在评论中提到的那样，设置堆大小的常用方法是选择k这样的2^k > currentSize. 如果输入项的大小足够大，代码的作者可能不会选择这种方法：

例如，在大多数情况下，预期输入大小约为 1200，峰值为 1500，而您的初始输入大小为 1025 个元素。通过通常的方法，您必须选择 k=11 -> size is 2048 但这意味着您浪费了 (2048 - 1500 = 548) * 内存中 AnyType 对象字节的大小。

于 2013-03-22T13:57:46.650 回答