Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: "Sven R. Kunze" Newsgroups: comp.lang.python Subject: Re: How to remove item from heap efficiently? Date: Tue, 12 Jan 2016 17:18:50 +0100 Lines: 25 Message-ID: References: <568EEC40.7070807@mail.de> <568FE797.6090808@mail.de> <5692A795.3070904@mail.de> Mime-Version: 1.0 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.uni-berlin.de uzmHg2i+mv61NSEptikk2QpsPvuAhABErLKH573qUWzA== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.008 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'open-source': 0.04; 'pypi': 0.07; 'cc:addr:python-list': 0.09; 'subject:How': 0.09; 'underlying': 0.09; '_heapq': 0.16; 'heap': 0.16; 'heapq': 0.16; 'jumping': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'subject:item': 0.16; 'subject:remove': 0.16; 'wrote:': 0.16; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; 'issue.': 0.20; 'to:2**1': 0.21; '(by': 0.22; 'cc:no real name:2**0': 0.22; "haven't": 0.24; 'header:In-Reply-To:1': 0.24; "i've": 0.25; 'header:User-Agent:1': 0.26; 'least': 0.27; '"remove': 0.29; 'that.': 0.30; 'another': 0.32; 'though,': 0.32; 'lets': 0.33; 'received:10.0': 0.34; 'so,': 0.35; 'best,': 0.35; 'unknown': 0.35; 'quite': 0.35; 'something': 0.35; 'item': 0.35; 'subject:?': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'thanks': 0.37; 'thought': 0.37; 'subject:from': 0.39; 'well.': 0.40; 'received:de': 0.40; 'skip:u 10': 0.61; 'replying': 0.61; 'here.': 0.62; 'charset:windows-1252': 0.62; 'past,': 0.66; 'hand': 0.82; 'late,': 0.84; 'researching': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=mail.de; s=mail201212; t=1452615534; bh=2Ky3mZoizrEvI/3RrLnUR+ajttnGQ3zhkmqcTf8MvM0=; h=Subject:To:References:Cc:From:Date:In-Reply-To:From; b=oC6otJmrvkeSx2DaBisvJeXephkY7+0mwKGge9g8xekbs5JxpOC0vBGS5isdocovX JHhDMNFrQiuoEYAbBUrn0PUeY3d3TLfvZxCcQTQBUrWZtGjyCdVQU9OsJuA7gIUq4L BjGjJUjZl0QUFIzyZYgPNqOV7OOUId7XNSE3c1WU= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.4.0 In-Reply-To: X-purgate: clean X-purgate: This mail is considered clean (visit http://www.eleven.de for further information) X-purgate-type: clean X-purgate-Ad: Categorized by eleven eXpurgate (R) http://www.eleven.de X-purgate: This mail is considered clean (visit http://www.eleven.de for further information) X-purgate: clean X-purgate-size: 918 X-purgate-ID: 154282::1452615533-000018ED-AC79F4D8/0/0 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Xref: csiph.com comp.lang.python:101549 On 12.01.2016 03:48, Cem Karan wrote: > > Jumping in late, but... > > If you want something that 'just works', you can use HeapDict: > > http://stutzbachenterprises.com/ > > I've used it in the past, and it works quite well. I haven't tested its asymptotic performance though, so you might want to check into that. Thanks for replying here. I've come across these types of wrappers/re-implementations of heapq as well when researching this issue. :) Unfortunately, they don't solve the underlying issue at hand which is: "remove item from heap with unknown index" and be efficient at it (by not using _heapq C implementation). So, I thought I did another wrapper. ;) It at least uses _heapq (if available otherwise heapq) and lets you remove items without violating the invariant in O(log n). I am going to make that open-source on pypi and see what people think of it. Best, Sven