Python的heapify()与列表推导和切片不兼容吗？

Question

我在一个自己写的程序里发现了一个有趣的bug，感觉自己可能理解错了。简单来说，Python的heapq模块并不是把列表排好序，而是以一种堆的方式来处理这个列表。具体来说，我原本以为heapify()会把列表变成一个有序的列表，这样在使用列表推导式时就能按顺序处理。

用Python文档里的优先队列作为例子：

from heapq import heapify, heappush, heappop
from random import shuffle

class Item(object):
    def __init__(self, name):
        self.name = name

lst = []

# iterate over a pseudo-random list of unique numbers
for i in sample(range(100), 15):
    it = Item("Some name for %i" % i)
    heappush(lst, (i, it))

print([i[0] for i in lst])

结果是

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

我们注意到，这并不是列表的原始顺序，而是某种堆的顺序，正如这里所描述的那样。我本来以为它会完全排好序。

作为测试，把列表传给heapify()后没有任何变化（因为列表已经是堆的顺序了）：

heapify(lst)

print([i[0] for i in lst])

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

而使用heappop()函数遍历这个列表时，结果就会按预期的顺序排列：

lst2 = []
while lst: lst2.append(heappop(lst))

print([i[0] for i in lst2])

>>> [2, 7, 10, 22, 27, 32, 33, 40, 45, 51, 67, 69, 89, 94, 97]

所以，看起来heapq并没有真正地把列表排好序（至少不是我们通常理解的那种排序），而是heappush()和heappop()这两个函数能够处理这种堆的顺序列表。

结果是：对一个堆化的列表进行切片和列表推导操作会得到无序的结果。

这是真的吗？而且这总是这样吗？

(顺便提一下：我在WinXP系统上使用的是Python 3.0.1)

Answer 1

结果是：对一个经过堆排序的列表进行切片和列表推导操作时，得到的结果是无序的。

这是真的吗？这总是这样吗？

如果你只是想得到一个一次性的排序列表，可以使用：

myList.sort()

优先队列/堆可以用来实现排序，或者可以用来保持一个优先级队列。往堆里插入数据的时间复杂度是O(lg n)，获取数据的时间复杂度是O(1)，而移除数据的时间复杂度也是O(lg n)。这比一次又一次地对整个列表进行排序要好得多。

Answer 2

“我原本以为heapify()会生成一个有序的列表，这样在进行列表推导时可以按顺序处理。”如果这个想法是根据手册的内容得出的，那你应该向文档反馈这个问题。

“结果是：对一个经过堆化的列表进行切片和列表推导操作，得到的结果是无序的。这是真的吗？这总是这样吗？”就像random.shuffle()一样，提到的操作并没有被定义为会产生“有序”的结果。它可能偶尔会产生“有序”的结果，但这只是巧合，不能依赖，也不值得去问（这是我的个人看法）。

Answer 3

堆并不是一个排好序的列表（它其实是一个部分排序的二叉树的表现形式）。

所以没错，如果你期待一个堆的列表像一个排好序的列表那样工作，你会感到失望。你能对堆做的唯一排序假设就是 heap[0] 总是它最小的元素。

（你已经写得很好了，我也没什么好补充的——你的问题已经很清楚地说明了事情的真相。8-）