将一个元素插入堆涉及将其附加到数组的末尾，然后向上传播，直到它在“正确的位置”并满足堆属性，其操作是 O(logn)。
但是，例如，在 C 中，realloc为了调整新元素的数组大小而调用可能（并且可能会）导致必须将整个数组复制到内存中的另一个位置，最好是 O(n)最坏的情况，对吧？
C（或任何语言）中的堆是否通常以固定的、预先分配的大小完成，或者复制操作是否无关紧要，足以使动态大小的堆成为可行的选择（例如，二进制堆以保持快速可搜索的项目列表）？
问问题
88 次
1 回答
2
一个典型的方案是在空间用完时将尺寸加倍。这种翻倍——以及随之而来的复制——确实需要 O(n) 时间。
但是，请注意，您不必经常执行此加倍操作。如果将所有在堆上执行的不涉及加倍的操作的所有加倍的总成本平均起来，那么成本确实是无关紧要的。（这种平均称为摊销分析。）
于 2012-06-05T13:50:51.643 回答