代码之家 › 专栏 › 技术社区 › Lay González

如果底层数据结构是一个列表,heapq的push操作怎么可能是O(logn)时间?

heapq time-complexity python

Lay González · 技术社区 · 4 年前

列表不需要O(n)时间来增加它的大小吗?那么,怎么可能呢堆.堆是O(logn)?

1 回复 | 直到 4 年前

ShadowRanger 4 年前

A list 摊销 O(1) 每隔很长一段时间,它都需要扩展底层容量,但通常 append 只需要声明已经分配的容量。

heapq.heappush 将招致 O(n) 努力重新分配底层 列表 的存储,但绝大多数时间,添加额外的项目(通过内部)是 ,后面跟着一个 O(log n) sift down操作将其移动到堆中的正确位置(重新建立堆不变量);sift down操作是通过元素交换实现的,这些都是 ,而不是插入和删除每个)

推荐文章

Google User · Django管理员在`list_display中未显示`creation_date`字段`

3 月前

user29747013 · 如何创建一个新的数据框架,其中包含原始数据框架中列的聚合列?

4 月前

ÎÎÎ½Î· ÎÎ®Î¹Î½Î¿Ï · Python lxml.html语法错误:使用lxml find时XPATH的谓词无效

4 月前

user29715306 · from_users=和chats=电视节目中的差异

4 月前

Redshoe · 当执行numpy.genfromtxt()时,python是否会读取文件的所有行?

4 月前

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

4 月前

prayner · 更新嵌套字典包含列表中的项

4 月前

Bringo Jr · 我可以在O(n)中解决这个问题吗?

4 月前

Dave · 如何在for循环中修改列表值

4 月前

Shukurullox Komiljonov · 从记录中获得相互和解。使用SQL

4 月前