Как перебрать 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 / потерю данных ?

Если нет, как я могу эффективно имитировать желаемое поведение?

Решение, которое я придумал, заключается в создании временной кучи, pu sh к нему, когда я вырываюсь из исходной кучи, и как только я закончу итерацию, установите исходную кучу равной временной куче.

Конечно, это не очень эффективно, и изменяет объект, который исходная куча ссылка.

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 ничего особенного, кстати, это просто просто список . Также обратите внимание, что куча - это структура данных, предназначенная для эффективного доступа к наименьшему (или наивысшему) значению, а не для повторения полностью. По сути, это бинарное дерево, каждый уровень которого расположен в виде списка в порядке глубины.