为什么在Python中，heappop的时间复杂度是O(logn)而不是O(n)？

Question

对于一个列表，heappop将弹出前面的元素。从列表前面删除一个元素的时间复杂度为O(n)。 我有没有遗漏什么？

- Alchemist

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

请注意，弹出操作不会移动大多数元素（例如，在heappop之前和之后，248位于同一位置）。

- Raymond Hettinger

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向你返回第一个元素，但不是通过移动整个数组来实现的。

- Josh Lee

Answer 3

堆的弹出操作的时间复杂度确实为 O(logn)。

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

- llllllllll

---

是的，那是最清晰的解释正在发生的事情。heappop() 会重新排列列表中 log(n) 个元素。 - Raymond Hettinger

Answer 4

看一下heapq.heappop的实现：https://svn.python.org/projects/python/trunk/Lib/heapq.py

它并不是从列表的前面删除一个元素，而是返回它并用其他东西替换它，这需要O(logn)的时间，并通过删除最后一个元素来减少底层列表的长度。

- Robin Davis

---

堆的弹出操作的时间复杂度永远不是常数时间。 - llllllllll

@liliscent，没错，我的句子可能措辞不当，我的意思是“从底层列表中删除最后一个元素是常数时间”。我会进行编辑。 - Robin Davis