我在一个我有点懒惰地实现的程序中发现了一个有趣的错误,我想知道我是否正确理解了它。简短的版本是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()
andheappop()
函数能够理解堆排序的列表。
结果:堆化列表上的任何切片和列表理解操作都将产生无序结果。
这是真的吗?这总是真的吗?
(顺便说一句:WinXP 系统上的 Python 3.0.1)