Python：heapq.heappop() 返回奇怪的结果

Question

我正在尝试在我的程序中使用Python模块heapq，但是当我使用heapq.heappop()时遇到了一个奇怪的问题。这个函数似乎没有返回堆中最小的元素。请看下面的代码:

Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import heapq
>>> list = [[1326, 'a'], [654, 'b']]
>>> print heapq.heappop(list)
[1326, 'a']
>>> print heapq.heappop(list)
[654, 'b']

heappop()不应该先返回[654, 'b']然后再返回[1326, 'a']吗？

- jpaulus

Answer 1

首先，您需要对列表进行堆化（原地操作）："heapify"：

In [1]: import heapq

In [2]: l = [[1326, 'a'], [654, 'b']]

In [3]: heapq.heapify(l)

In [4]: heapq.heappop(l)
Out[4]: [654, 'b']

In [5]: heapq.heappop(l)
Out[5]: [1326, 'a']

同时，避免将列表命名为list - 这会导致您掩盖内置的list关键字。

- alecxe

---

谢谢，确实是上面例子的问题。对于我的代码，我发现每次编辑堆后都需要再次使用sort()函数（我太傻了）。 - jpaulus