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

Groups > comp.lang.python > #101375

Re: How to remove item from heap efficiently?

Path csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From Peter Otten <__peter__@web.de>
Newsgroups comp.lang.python
Subject Re: How to remove item from heap efficiently?
Date Fri, 08 Jan 2016 14:26:28 +0100
Organization None
Lines 20
Message-ID <mailman.68.1452259606.2305.python-list@python.org> (permalink)
References <568EEC40.7070807@mail.de>
Mime-Version 1.0
Content-Type text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding 7Bit
X-Trace news.uni-berlin.de eHYATxsvYlPzy+HbNIxOLwO/cGuUfHhg/Zu+rc9DckTg==
Return-Path <python-python-list@m.gmane.org>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.000
X-Spam-Evidence '*H*': 1.00; '*S*': 0.00; 'everybody,': 0.07; 'subject:How': 0.09; 'marking': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'timestamp': 0.09; '(say': 0.16; 'heapq': 0.16; 'popping': 0.16; 'priority).': 0.16; 'received:80.91.229.3': 0.16; 'received:dip0.t-ipconnect.de': 0.16; 'received:io': 0.16; 'received:plane.gmane.org': 0.16; 'received:psf.io': 0.16; 'received:t-ipconnect.de': 0.16; 'subject:item': 0.16; 'subject:remove': 0.16; 'wrote:': 0.16; 'header:User-Agent:1': 0.26; 'header:X-Complaints-To:1': 0.26; 'actual': 0.28; 'mention': 0.30; 'option': 0.31; 'another': 0.32; 'lists': 0.34; 'item': 0.35; 'problem.': 0.35; 'there': 0.36; 'to:addr:python-list': 0.36; 'subject:?': 0.36; 'subject:: ': 0.37; 'two': 0.37; 'received:org': 0.37; 'subject:from': 0.39; 'to:addr:python.org': 0.40; 'where': 0.40; 'received:de': 0.40; 'oldest': 0.66
X-Injected-Via-Gmane http://gmane.org/
X-Gmane-NNTP-Posting-Host p57bd972e.dip0.t-ipconnect.de
User-Agent KNode/4.13.3
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.20+
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>
Xref csiph.com comp.lang.python:101375

Show key headers only | View raw

Sven R. Kunze wrote:

> Hi everybody,
> 
> suppose, I need items sorted by two criteria (say timestamp and
> priority). For that purpose, I use two heaps (heapq module):
> 
> heapA # items sorted by timestamp
> heapB # items sorted by priority
> 
> Now my actual problem. When popping an item of heapA (that's the oldest
> item), I need to remove the very same item from heapB, regardlessly
> where it is in heapB. And vice versa.
> 
> Is there a datastructure or a simple trick to achieve that in an
> efficient matter?

The heapq docs mention marking as deleted as an alternative to removing.
Another option is to try sorted lists and bisect.

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

Thread

Re: How to remove item from heap efficiently? Peter Otten <__peter__@web.de> - 2016-01-08 14:26 +0100

csiph-web