walking a heapq nondestructively without duplicating?
Ned Batchelder
ned at nedbatchelder.com
Fri Sep 27 19:08:02 EDT 2013
On 9/27/13 6:22 PM, Tim Chase wrote:
> I've got a large heapq'ified list and want to walk it in-order
> without altering it. I get the "unsorted" heap'ish results if I just
> do
>
> from heapq import heappush, heappop, nlargest, nsmallest
> my_heap = []
> for thing in lots_of_items():
> heappush(thing)
> for item in my_heap:
> ...
>
> To get them in-order, I can do something like
>
> while my_heap:
> item = heappop(my_heap)
> do_something(item)
>
> to iterate over the items in order, but that destroys the original
> heap. I can also do
>
> for item in nlargest(len(my_heap), my_heap): # or nsmallest()
> do_something(item)
>
> but this duplicates a potentially large list according to my
> reading of the description for nlargest/nsmallest[1]. Is there a
> handy way to non-destructively walk the heap (either in-order or
> reversed) without duplicating its contents?
If you add all your items at once, and then you want to walk over all
the items, then don't use a heap. Just put all your items in a list,
and then sort it. The advantage of a heap is that you can add items to
it with little effort, delaying some of the work until when you need to
get the items out. It maintains a partially-sorted list that's good for
insertion and popping. You have different needs. Use a sorted list.
--Ned.
> -tkc
>
> [1] http://docs.python.org/2/library/heapq.html#heapq.nlargest
>
>
>
>
>
>
>
More information about the Python-list
mailing list