Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!us.feeder.erje.net!news2.arglkargh.de!news.mixmin.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python.list@tim.thechases.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.071
X-Spam-Evidence: '*H*': 0.86; '*S*': 0.00; 'iterate': 0.09; '(either': 0.16; '-tkc': 0.16; 'duplicates': 0.16; 'from:addr:python.list': 0.16; 'from:addr:tim.thechases.com': 0.16; 'from:name:tim chase': 0.16; 'heap': 0.16; 'heapq': 0.16; 'nsmallest': 0.16; 'import': 0.22; "i've": 0.25; '[1]': 0.29; 'url:python': 0.33; 'something': 0.35; 'but': 0.35; 'there': 0.35; 'charset:us-ascii': 0.36; 'subject:?': 0.36; 'url:org': 0.36; 'list': 0.37; 'url:library': 0.38; 'to:addr:python-list': 0.38; 'to:addr:python.org': 0.39; 'according': 0.40; 'skip:n 10': 0.64; 'results': 0.69; 'walk': 0.74; 'potentially': 0.81; 'received:50.22': 0.84; 'subject:skip:n 10': 0.84
Date: Fri, 27 Sep 2013 17:22:14 -0500
From: Tim Chase <python.list@tim.thechases.com>
To: python-list@python.org
Subject: walking a heapq nondestructively without duplicating?
X-Mailer: Claws Mail 3.8.1 (GTK+ 2.24.10; x86_64-pc-linux-gnu)
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname - boston.accountservergroup.com
X-AntiAbuse: Original Domain - python.org
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - tim.thechases.com
X-Get-Message-Sender-Via: boston.accountservergroup.com: none
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.395.1380320435.18130.python-list@python.org>
Lines: 38
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1380320435 news.xs4all.nl 15938 [2001:888:2000:d::a6]:53810
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:54915

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?

-tkc

[1] http://docs.python.org/2/library/heapq.html#heapq.nlargest