如何在不丢失数据的情况下迭代heapq？

Question

在 Python 3 中，我像这样使用 heapq：

import heapq

heap = [3]
heapq.heapify(heap)
heapq.heappush(heap, 5)
# Push more values...

# I can iterate heap like so, but by the end it will be empty:
while (heap):
    curr = heapq.heappop(heap)
    # Do whatever with curr

有没有办法迭代 heapq 以便我按排序顺序获取值而不会改变 heapq/丢失数据？

如果没有，我怎样才能有效地模仿所需的行为？

我想出的解决方案是创建一个临时堆，在我从原始堆中弹出时推送到它，一旦我完成迭代，将原始堆设置为等于临时堆。

当然这不是很有效，而且改变了原始堆引用的对象。

temp = []
heapq.heapify(temp)

while(heap):
    curr = heapq.heappop(heap)
    heapq.heappush(temp, curr)
    # Do whatever with curr
heap = temp

Answer 1

如果你想要的只是堆上的所有值，按排序顺序，那么只需对 heap 进行排序。Usingsorted()为您提供排序顺序的序列，而不改变堆列表本身：

sorted(heap)

或者，由于按排序顺序的列表也是有效堆，因此对堆进行原地排序：

heap.sort()

使用的排序算法TimSort受益于堆结构中固有的偏序，并且肯定比从堆中一个一个地弹出值然后构造一个新堆更有效。

该heap值本身是没有什么特别的，顺便说一句，这只是一个列表。另请注意，堆是一种数据结构，旨在让您有效地访问最低（或最高）值，而不是完全迭代。它本质上是一棵二叉树，树的每一层都按深度顺序排列成一个列表。