4

我在一个我有点懒惰地实现的程序中发现了一个有趣的错误,我想知道我是否正确理解了它。简短的版本是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)

4

4 回答 4

9

堆不是排序列表(它是部分排序二叉树的表示)。

所以是的,你是对的,如果你期望一个 heapified 列表表现得像一个排序列表,你会失望的。您可以对堆做出的唯一排序假设是它heap[0]始终是它的最小元素。

(很难在您已经写的内容上添加太多内容 - 您的问题是关于“事物现状”的优秀文章。8-)

于 2009-06-25T23:23:49.367 回答
0

结果:堆化列表上的任何切片和列表理解操作都将产生无序结果。

这是真的吗?这总是真的吗?

如果您只想获得一次性排序列表,请使用:

myList.sort()

优先级队列/堆可用于实现排序,或者它们可用于将队列保持为优先级形式。插入堆是 O(lg n),获取是 O(1),删除是 O(lg n),这比一遍又一遍地使用整个列表要好得多。

于 2009-06-25T23:30:05.203 回答
0

“ 结果:对堆化列表进行任何切片和列表理解操作都会产生无序结果。这是真的吗,而且总是这样吗?” 不,这并不总是正确的。虽然它大部分时间都是不订购的,但它有可能被订购。heapify() 产生一个满足“堆不变量”的列表。在这种情况下,它是一个最小堆。事实证明,排序列表也满足堆不变量(参见heapq第 4 段:“heap.sort() 保持堆不变量”)。所以理论上,一个堆积列表也可能会被排序。

于 2009-06-26T04:13:54.960 回答
0

"""我期待 heapify() 生成一个有序列表,以有序的方式促进列表理解。""":如果这个期望是基于对手册的阅读,你应该提出一个文档错误报告。

""" 结果:对堆化列表的任何切片和列表理解操作都会产生无序结果。这是真的吗,而且总是如此吗?""":就像 random.shuffle() 一样,提到的活动是未定义为产生“有序”结果。它可能偶尔会产生“有序”的结果,但这是巧合,不值得依赖也不值得询问(恕我直言)。

于 2009-06-26T00:11:15.153 回答