python - 如何在不丢失数据的情况下迭代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

如果您想要的只是堆上的所有值，按排序顺序，那么只需对堆进行排序。使用 sorted()在不改变堆列表本身的情况下按排序顺序为您提供序列:

sorted(heap)

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

heap.sort()

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

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