Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #54917

Re: walking a heapq nondestructively without duplicating?

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: walking a heapq nondestructively without duplicating? Ned Batchelder <ned@nedbatchelder.com> - 2013-09-27 19:08 -0400

csiph-web