为什么在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之前和之后在同一位置）。

Answer 2

如果您正在考虑做什么list.pop，该文档会有些误导。

如果heap是 minheap，则heap[0]确实是最小的项。Python 的list.pop方法返回列表的最后一个元素，但heapq.heappop返回堆的最小（第一个！）元素。但是，它通过弹出堆的最后一个元素（这是对列表的 O(1) 操作），将其与 交换heap[0]，冒泡（这是 O(log n)），然后返回值来实现这一点从heap[0]呼叫者中删除。

所以：list.pop返回列表中的最后一项，并且是O(1)。heapq.heappop将第一项返回给您，但不是通过移动整个数组。

Answer 3

堆弹出确实很O(logn)复杂。

您缺少的是，从堆中弹出并不像“删除第一个元素并将所有元素左移一个”。有一种算法可以在列表内移动元素，弹出后，不能保证列表中剩余元素的顺序与之前相同。