Python 的 heapify() 不能很好地处理列表理解和切片吗？
我在一个程序中发现了一个有趣的错误，我有点懒惰地实现了它，并想知道我是否正确理解它。 简而言之，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）
I found an interesting bug in a program that I implemented somewhat lazily, and wondered if I'm comprehending it correctly. The short version is that Python's heapq implementation doesn't actually order a list, it merely groks the list in a heap-centric way. Specifically, I was expecting heapify() to result in an ordered list that facilitated list comprehension in an ordered fashion.
Using a priority cue example, as in the Python documentation:
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])
Results in
>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]
This, we note, is not the original ordering of the list, but apparently some heap-centric ordering as described here. I was lazily expecting this to be fully ordered.
As a test, running the list through heapify() results in no change (as the list is already heap-ishly ordered):
heapify(lst)
print([i[0] for i in lst])
>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]
Whereas iterating through the list with the heappop() function results in ordering as expected:
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]
So, it would seem that heapq does not order a list (at least in the human sense of the word), but rather the heappush() and heappop() functions are able to grok the heap-ishly ordered list.
The result: Any slicing and list comprehension operations on a heapified list will yield non-ordered results.
Is this true, and is this always true?
(BTW: Python 3.0.1 on a WinXP system)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
堆不是排序列表（它是部分排序二叉树的表示）。
所以是的，你是对的，如果你期望堆化列表表现得像排序列表，你会失望的。 您可以对堆做出的唯一排序假设是
heap[0]始终是其最小元素。（很难在你已经写的内容上添加太多内容 - 你的问题是对事情是怎样的精彩描述。8-）
A heap is not a sorted list (it's a representation of a partially sorted binary tree).
So yes, you're right, if you expect a heapified list to behave like a sorted list, you'll be disappointed. The only sorting assumption you can make about a heap is that
heap[0]is always its smallest element.(It's difficult to add much to what you've already written - your question is an excellent writeup of How Things Are. 8-)
如果您只想获得一次性排序列表，请使用：
优先级队列/堆可用于实现排序，或者它们可用于将队列保持为优先级形式。 向堆中插入的时间复杂度为 O(lg n)，获取的时间复杂度为 O(1)，删除的时间复杂度为 O(lg n)，这比一遍又一遍地使用整个列表要好得多。
If you just want to get a one-time sorted list, use:
Priority queues/heaps can be used to implement a sort, or they can be used to keep a queue in priority form. Insertions into a heap are O(lg n), gets are O(1), and removals are O(lg n), which is a lot better than just resorting the entire list over and over again.
“”“我期望 heapify() 生成一个有序列表，从而以有序方式促进列表理解。”“”：如果此期望是基于阅读手册，则您应该提出文档错误报告。
""" 结果：堆化列表上的任何切片和列表理解操作都会产生无序结果。这是真的吗，并且总是这样吗？"""：就像 random.shuffle() 一样，提到的活动是未定义为产生“有序”结果。 它可能偶尔会产生“有序”结果，但这是巧合，不值得依赖，也不值得询问（恕我直言）。
"""I was expecting heapify() to result in an ordered list that facilitated list comprehension in an ordered fashion.""": If this expectation was based on a reading of the manual, you should raise a docs bug report.
""" The result: Any slicing and list comprehension operations on a heapified list will yield non-ordered results. Is this true, and is this always true?""": Just like e.g. random.shuffle(), the mentioned activity is not defined to produce "ordered" results. It may produce "ordered" results occasionally, but this is coincidental and not to be relied on and not worth asking (IMHO).
“结果：堆化列表上的任何切片和列表理解操作都会产生无序结果。这是真的吗？并且总是如此吗？” 不，这并不总是正确的。 虽然大多数时候是非订购的，但也有可能订购。 heapify() 生成一个满足“堆不变量”的列表。 在这种情况下，它是一个最小堆。 事实证明，排序列表也满足堆不变量（参见 heapq 第 4 段： “heap.sort() 保持堆不变性”）。 因此从理论上讲，堆化列表也可能会被排序。
" The result: Any slicing and list comprehension operations on a heapified list will yield non-ordered results. Is this true, and is this always true?" No, it is not always true. Although it will be non-ordered most of the time, it is possible for it to be ordered. heapify() produces a list that satisfies the "heap invariant". In this case, it is a min-heap. It turns out that a sorted list also satisfies the heap invariant (see heapq paragraph 4: "heap.sort() maintains the heap invariant"). So in theory it is possible that a heapified list will also happen to be sorted.