0

列表不需要 O(n) 时间来增加其大小吗？那么 heap.heappush 怎么可能是 O(log n) 呢？

4

1 回答 1

2

Alist已摊销 O(1)附加；每隔一段时间，它就需要扩展底层容量，但通常append只需要声明已经分配的容量。

所以是的，每隔一段时间，heapq.heappush就会产生O(n)重新分配底层list存储的工作，但是绝大多数时候，添加额外的项目（通过append内部完成）是O(1)，然后是一个O(log n)筛选操作来移动它到堆中的正确位置（重新建立堆不变量）；筛选操作是通过元素交换实现的，它们都是O(1)，而不是插入和删除（O(n)每个都是）

于 2020-11-04T04:00:54.690 回答