对于一个列表,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, 335, 248, 336, 540, 413, 595, 405, 470, 592, 963, 566, 484, 970]
>>> # ^----^---------^----^----^----^----^---------^----^----^--- elements that didn't move
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
向你返回第一个元素,但不是通过移动整个数组来实现的。堆的弹出操作的时间复杂度确实为 O(logn)
。
你所忽略的是,从堆中弹出元素并非像“删除第一个元素并将所有元素左移一位”那样简单。有一种算法可以在列表内移动元素,在弹出后,不能保证列表中剩余的元素与之前的顺序相同。
看一下heapq.heappop的实现:https://svn.python.org/projects/python/trunk/Lib/heapq.py
它并不是从列表的前面删除一个元素,而是返回它并用其他东西替换它,这需要O(logn)的时间,并通过删除最后一个元素来减少底层列表的长度。