假设我们有一个充当隐式二进制堆的数组，我们从以下内容开始:
[0，0，0]
它慢慢地被填满到:
[3，2，3]
我们需要通过将其复制到大小为2n+1的新增长数组中来增长它，其中n是旧数组的长度，但这一次我们将一些元素块复制到增长的数组中的确定位置，例如:
[0，3，0，2，3，0，0]
假设上面的数组被填满，我们需要再次增长，它将如下所示:
[5，3，5，2，3，4，5]
|
|
\|/
[0，5，0，3，5，0，0，2，3，4，5，0，0，0，0，0]
我希望你现在已经了解了转变的模式.
那么，有没有办法使用System.arrayCopy()在o(log(N))中实现这种模式转换呢？如果没有，你能建议其他 Select 吗？
这里有几点需要注意.
Firstly,遵循通常的策略，即拥有一个可以有效地向右扩展的array.
一个例子是C++中的std::vector.
稍微简化一下，该数组具有显式大小和隐式容量.
分配的内存与容量匹配.
已用内存与大小匹配.
当我们扩展数组并且大小小于容量时，我们将开始使用下一个分配的元素，即O(1)成本.
当大小等于容量时，我们创建一个大两倍的副本，将内容移到那里，然后开始使用新副本.
请注意，此操作为O(大小). 但由于它发生在容量1，2，4，8，16，32…，total running time也是O(大小). 这就是所谓的amortized complexity O(1). 形式上，对于每k个运算，前k个运算在O(K)时间内完成. 有些手术费用很高，但却很少见.
有一些方法可以获得一个可扩展的数组，其中每个操作的成本是实数O(1)，而不是摊销，代价是更大的常量因子. 一种这样的方法是提前创建下一个数组，同时维护该数组的两个副本，并且每次添加一个时，还将另外两个元素复制到下一个数组中. 然而，如果这将是焦点，那么它应该得到一个单独的问题.
Secondly,展开底层容器后，无论如何都可以在O(Logn)内高效地将元素插入到二进制堆中. 只需将该元素添加为最后一个元素，然后筛选它，直到它停止. 因此，如果我们对每个操作amortized O(log n)个满意，我们可以只使用上面的策略进行扩展和自然的堆插入操作.唯一的问题是，如果我们想要真正的O(Logn)，而不是摊销，那么它应该在问题中明确提到.
Thirdly,如果您坚持对集装箱扩展的要素进行重新排序，其成本与集装箱扩展成本相同. 记住，在每次扩展时，我们必须将旧内容复制到新数组中，这需要O(大小)时间. 嗯，在这个时刻，我们可以只复制到我们 Select 的地方，而不是相同的地方. 在您的示例中，我们 Select [0]->；[1]、[1，2]->；[3，4]、[3，4，5，6]->；[7，8，9，10]等等.
如果确实需要，就像每个元素加法将摊销的O(1)转换为实数O(1)一样，我们可以提前创建下一个数组，并在每次加法时再复制两个元素. 但是，我们必须维护这两个副本，所以堆操作的O(Logn)也将具有更大的常量因子.