为什么heappop时间复杂度在python中是O(logn)(不是O(n))？

发布时间：2020-12-20 11:02:36 所属栏目：Python 来源：网络整理

导读：对于列表,heappop将弹出前面的元素.从列表前面删除元素的时间复杂度为O(n). 我想念什么吗？解决方法一个heappop()重新排列列表中的log(n)元素,这样它就不必移动每个元素. 这很容易看出： from random import randrange from heapq import heapify,heappop

对于列表,heappop将弹出前面的元素.从列表前面删除元素的时间复杂度为O(n).
我想念什么吗？

解决方法

一个heappop()重新排列列表中的log(n)元素,这样它就不必移动每个元素.

这很容易看出：

>>> from random import randrange
>>> from heapq import heapify,heappop
>>> h = [randrange(1000) for i in range(15)]
>>> heapify(h)
>>> h
[80,126,248,336,335,413,595,405,470,592,540,566,484,970,963]
>>> heappop(h)
80
>>> h
[126,963,970]
>>> #       ^----^---------^----^----^----^----^---------^----^----^--- elements that didn't move

请注意,弹出操作没有移动大多数元素(例如248在heappop之前和之后处于相同位置).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!