2

在 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
4

2 回答 2

5

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

sorted(heap)

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

heap.sort()

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

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

于 2020-01-24T21:36:42.713 回答
0

只需复制基础列表，即temp = copy(heap)像您一样迭代它，即通过

while(temp):
    curr = heapq.heappop(temp)

虽然副本是O(N)，但遍历将是O(N log N)。因此，如何遍历 a 仍然存在heapq问题O(N)。

于 2022-01-05T13:44:39.073 回答