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: Fri, 8 Jan 2016 17:52:28 +0100 Lines: 28 Message-ID: References: <568EEC40.7070807@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 KVlcgyEC1w8ggteY/0pbfgTCPAIkqeMSBHE1RNxau8sA== 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; 'everybody,': 0.07; 'subject:How': 0.09; 'insertion': 0.09; 'marking': 0.09; 'timestamp': 0.09; '(say': 0.16; '14:26,': 0.16; 'heap': 0.16; 'heapq': 0.16; 'popping': 0.16; 'priority).': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'subject:item': 0.16; 'subject:remove': 0.16; 'wrote:': 0.16; 'header:In-Reply-To:1': 0.24; 'header:User-Agent:1': 0.26; 'then.': 0.27; 'actual': 0.28; 'periodic': 0.29; 'mention': 0.30; 'option': 0.31; 'another': 0.32; 'up.': 0.32; 'received:10.0': 0.34; 'lists': 0.34; 'best,': 0.35; 'item': 0.35; 'problem.': 0.35; 'reply.': 0.35; 'there': 0.36; 'to:addr:python-list': 0.36; 'subject:?': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'really': 0.37; 'two': 0.37; 'thanks': 0.37; 'subject:from': 0.39; 'to:addr:python.org': 0.40; 'where': 0.40; 'received:de': 0.40; 'your': 0.60; 'charset:windows-1252': 0.62; 'oldest': 0.66; 'grow': 0.75; 'otten': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=mail.de; s=mail201212; t=1452271951; bh=M8BZF3vHyoIosy9RtFWW0q0Va2S4h0xVQvFMz5dUUYM=; h=Subject:To:References:From:Date:In-Reply-To:From; b=s9l/TrN9XvvCtYZqQyzYqHaBLjQDr6cyVLmJ7KrndQxeH2Nk2GQmUjFc9xnmtRDIy npBsatdtRRBgYcmMNQaJDnMbjm0FjbTujNdlhnoXFftREFZZ9ulXBjxKqqGZvvSqSA IwESSJbV5ntX4dUmQ6De+O3LJeSER8huSld7OZLA= 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: 925 X-purgate-ID: 154282::1452271950-000009F3-8336D5FE/0/0 X-Mailman-Approved-At: Sat, 09 Jan 2016 09:51:08 -0500 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:101404 Thanks for your reply. On 08.01.2016 14:26, Peter Otten wrote: > 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. That is how I do it for now. However, the heap continues to grow which needs a periodic clean up. > Another option is to try sorted lists and bisect. The docs tell me that insertion is not really fast then. :/ Best, Sven