Python的heapify（）与列表理解和切片不兼容吗？

我在一个程序中发现了一个有趣的错误，我有点懒惰地执行，并想知道我是否正确理解它。简短版本是Python's heapq implementation实际上并没有排序列表，它只是以堆为中心的方式列出列表。具体而言，我期待heapify()产生一个有序列表，以有序的方式促进列表理解。使用Python的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]

此，我们注意到，不在列表的原排序，但显然一些以堆为中心的排序为described here。我正在懒洋洋地期待这完全订购。

作为测试，通过heapify（）运行列表会导致没有变化（如列表已经堆ishly订购）：

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()功能能够饶有兴趣地列出堆。

结果：堆积列表上的任何切片和列表理解操作都会产生无序结果。

这是真的，这是总是是真的吗？

（顺便说一句：Python之3.0.1上的WinXP系统）

来源

2009-06-25 JohnMetta

堆不是排序列表（这是一个部分地排序的二进制树的表示）。

所以是的，你是对的，如果你期望一个heapified列表行为像一个排序列表，你会失望。关于堆的唯一排序假设是heap[0]始终是它的最小元素。

（这是很难多地增加你所编写的程序 - 你的问题的事物如何是一个很好的书面记录8-）

来源

2009-06-25 23:23:49 RichieHindle

是的，我主要发布它，以便在其他人有同样问题时可用，但很高兴知道我误解了这些文档，并且应该更清楚地阅读它们。 – JohnMetta 2009-06-26 14:48:41

其结果是：在任何切片和列表理解操作 heapified list将产生无序的结果。

这是真的，这是真的吗？

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

myList.sort()

优先级队列/堆可以被用来实现排序，或者它们可以被用来保持队列优先形式。插入到堆中的是O（lg n），get是O（1），并且清除是O（lg n），这比仅仅一遍又一遍地遍历整个列表好得多。

来源

2009-06-25 23:30:05

“”“我期待着heapify（）会产生一个有序的列表，以有序的方式促进列表理解。”“”：如果这个期望是基于手册的阅读，你应该提出一个文档错误报告。

“”“结果：堆积列表上的任何切片和列表理解操作都会产生无序结果。这是真的吗？”“”：就像random.shuffle（），所提及的活动未被定义为产生“有序”结果。它可能偶尔产生“有序”的结果，但这是巧合，不值得信赖和不值得问（恕我直言）。

来源

2009-06-26 00:11:15

“结果：堆积列表上的任何切片和列表理解操作都会产生无序结果。这是真的吗？这总是正确的吗？”不，这并非总是如此。虽然大部分时间它都是无序的，但它可能会被订购。 heapify（）生成一个满足“heap不变量”的列表。在这种情况下，它是一个小堆。事实证明，排序列表还满足堆不变量（请参见heapq段落4：“heap.sort（）维护堆不变量”）。所以在理论上，一个堆积列表也可能会被排序。

来源

2009-06-26 04:13:54 newacct

Python的heapify（）与列表理解和切片不兼容吗？

回答

相关问题