我正在使用动态数组来表示最小堆。有一个循环删除最小值，并将随机元素添加到最小堆，直到某些条件发生。虽然我不知道堆的长度在运行时会如何变化（有很多随机性），但我知道上限，即 1000 万。我有两个选择：
1)使用 malloc 声明一个小数组，然后在堆中的元素数量超过长度时调用 realloc。
2）使用malloc声明一个1000万条目数组。这避免了调用 realloc。
问题
选项 2 是否比选项 1 更有效？
我用我的代码对此进行了测试，使用 2 似乎显着减少了 (20%) 运行时间。这是由于代码中的随机性而估计的。用 malloc 预先声明一个 10-5000 万的大型条目数组有什么缺点吗？
如果您可以腾出内存来进行大量的前期分配，并且它提供了值得的性能提升，那么一定要这样做。
如果您坚持使用realloc，那么您可能会发现每次将大小加倍而不是增加固定数量可以在性能和有效内存使用之间取得良好的折衷。
不是说用realloc的时候，内存会从同一个地方扩展，也有可能会发生内存被移到另一个区域的情况。
因此，使用 realloc 可能会导致复制您之前拥有的内存块。
还要考虑系统调用可能需要一些开销，所以你最好调用一次 malloc 。
缺点是，如果您没有使用所有空间，您将占用大量可能需要的内存。如果您确切知道需要多少字节，由于系统调用开销，一次分配会更有效率，然后逐个分配它。通常你可能有一个上限但不知道确切的数字。花时间分配空间来处理上限可能需要 1 秒。但是，如果这种特殊情况只有上限的一半，则可能需要 0.75 秒来逐个分配。因此，这取决于您认为您将获得的上限有多接近。