Path: csiph.com!feeder.erje.net!2.eu.feeder.erje.net!newsfeed0.kamp.net!newsfeed.kamp.net!fu-berlin.de!uni-berlin.de!not-for-mail From: Cem Karan Newsgroups: comp.lang.python Subject: Re: How to remove item from heap efficiently? Date: Mon, 11 Jan 2016 21:48:34 -0500 Lines: 37 Message-ID: References: <568EEC40.7070807@mail.de> <568FE797.6090808@mail.de> <5692A795.3070904@mail.de> Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\)) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable X-Trace: news.uni-berlin.de fVq4VSdWwAdgVOWpHAhSqAPGgO0Ss0XKtHTpB6vQoFEA== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.012 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'cc:addr:python-list': 0.09; 'subject:How': 0.09; 'jan': 0.11; '2016': 0.16; 'amortized': 0.16; 'heap': 0.16; 'jumping': 0.16; 'o(len(heap))': 0.16; 'operation.': 0.16; 'received:192.168.1.4': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'subject:item': 0.16; 'subject:remove': 0.16; 'useless': 0.16; 'wrote:': 0.16; 'cc:addr:python.org': 0.20; 'cc:2**1': 0.22; 'cc:no real name:2**0': 0.22; 'am,': 0.23; 'split': 0.23; "haven't": 0.24; 'thanks,': 0.24; 'header:In-Reply-To:1': 0.24; "i've": 0.25; 'operations,': 0.27; 'that.': 0.30; 'becomes': 0.30; 'checks': 0.30; 'though,': 0.32; 'items.': 0.33; 'message-id:@gmail.com': 0.34; 'add': 0.34; 'received:google.com': 0.35; 'could': 0.35; 'done': 0.35; 'quite': 0.35; 'something': 0.35; 'received:209.85': 0.36; 'subject:?': 0.36; 'subject:: ': 0.37; 'method': 0.37; 'thanks': 0.37; 'charset:us-ascii': 0.37; 'doing': 0.38; 'received:209': 0.38; 'means': 0.39; 'subject:from': 0.39; 'received:192': 0.39; 'well.': 0.40; 'header:Message-Id:1': 0.61; 'more': 0.63; 'our': 0.64; 'past,': 0.66; 'complexity': 0.84; 'late,': 0.84; 'approached': 0.95 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=Y/BqU88X6ClKIYgmD/3QIlSk2y200xCuDv95Ng70nDg=; b=yZTgq6YpKGik04ld2r7qx04gFJi1OBhm5Q1QtMaYKsOlls6xLSPQoOPnhcW9WYkjFU ukEe7D+kpLzXxLfB+KtwfYdmYXRMfXlMoGJFN9StDrND+fXzhOJ6WDsdgrlRBbcLwScP HXFrs4rXKWkVqVyVnNOYJh2dTDowHL0gi4dS8oG0tCYNmqwlvlMLbVyua+6dU6h4kNvC hj1S7eJ6d5Ks+rHO9wWnf46vsRJpjiem/HBTKrvAU0DpIt/E9bBwlMZxvNgioDMSuWu0 bKxUSY51ZJS038Cwe1BnhtmgOkKF3YXS4lhjBxSlFu3F3h5l/PXvaTYF3YAoSgumMHbp XT3A== X-Received: by 10.140.93.117 with SMTP id c108mr165673349qge.101.1452566912030; Mon, 11 Jan 2016 18:48:32 -0800 (PST) In-Reply-To: X-Mailer: Apple Mail (2.1510) 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:101512 On Jan 11, 2016, at 9:53 AM, srinivas devaki = wrote: > On Jan 11, 2016 12:18 AM, "Sven R. Kunze" wrote: >> Indeed. I already do the sweep method as you suggested. ;) >>=20 >> Additionally, you provided me with a reasonable condition when to do = the > sweep in order to achieve O(log n). Thanks much for that. I currently = used > a time-bases approached (sweep each 20 iterations). >>=20 >> PS: Could you add a note on how you got to the condition ( > 2*self.useless_b > len(self.heap_b))? >>=20 >=20 > oh that's actually simple, > that condition checks if more than half of heap is useless items. > the sweep complexity is O(len(heap)), so to keep the extra amortized > complexity as O(1), we have to split that work(virtually) with = O(len(heap)) > operations, so when our condition becomes true we have done len(heap) > operations, so doing a sweep at that time means we splitted that > work(O(len(heap))) with every operation. 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, Cem Karan=