Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Sender: Ned Batchelder <nedbat@gmail.com>
Date: Fri, 27 Sep 2013 19:08:02 -0400
From: Ned Batchelder <ned@nedbatchelder.com>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:17.0) Gecko/20130801 Thunderbird/17.0.8
MIME-Version: 1.0
To: Tim Chase <python.list@tim.thechases.com>
Subject: Re: walking a heapq nondestructively without duplicating?
References: <20130927172214.1d9be803@bigbox.christie.dr>
In-Reply-To: <20130927172214.1d9be803@bigbox.christie.dr>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.397.1380323292.18130.python-list@python.org>
Lines: 49
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:54917

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
>
>
>
>
>
>
>