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

Question

对于列表，heappop 会弹出最前面的元素。从列表的前面删除一个元素的时间复杂度为 O(n)。我错过了什么吗？

Answer 1

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, 335, 248, 336, 540, 413, 595, 405, 470, 592, 963, 566, 484, 970]
>>> #       ^----^---------^----^----^----^----^---------^----^----^--- elements that didn't move

请注意，弹出操作并没有移动大部分元素(例如 248 在 heappop 之前和之后的相同位置)。