Python的heapify()不能很好地与列表理解和切片一起使用吗？

Question

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

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

所以,是的,你是对的,如果你期望一个堆化列表表现得像一个排序列表,你会感到失望.关于堆的唯一排序假设是它heap[0]始终是最小的元素.

(很难为你已经写过的内容添加很多内容 - 你的问题是关于事情的优秀写作.8-)