Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Cem Karan Newsgroups: comp.lang.python Subject: Re: Heap Implementation Date: Tue, 9 Feb 2016 19:41:20 -0500 Lines: 40 Message-ID: References: <56AD3D83.2050308@mail.de> <7C522D08-9D73-48D2-A71D-F1D1D34C02A5@gmail.com> <185DAEA4-8728-4792-A3B7-7F6AC5A7F876@gmail.com> <2308C08E-D2A1-4F16-800F-C2794D30F96B@gmail.com> <65105210-BAE5-4CD1-8C8C-73FC51982901@gmail.com> 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 wKcf8/FrtxWCbFy7LroRGQ0X3j6OdKan/oVWksgWmAIw== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.022 X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'cc:addr:python-list': 0.09; 'missed': 0.15; 'element.': 0.16; 'heap': 0.16; 'heap,': 0.16; 'received:192.168.1.4': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'wrote:': 0.16; 'element': 0.18; 'pointer': 0.18; '>>>': 0.20; '(not': 0.20; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; 'fix': 0.21; 'assuming': 0.22; 'constant': 0.22; 'lawrence': 0.22; 'cc:no real name:2**0': 0.22; 'am,': 0.23; 'feb': 0.23; 'thanks,': 0.24; 'header:In-Reply-To:1': 0.24; "i've": 0.25; 'figure': 0.27; 'queue': 0.29; "i'm": 0.30; 'problem': 0.33; 'url:python': 0.33; 'message-id:@gmail.com': 0.34; 'changing': 0.34; 'add': 0.34; 'that,': 0.34; 'received:google.com': 0.35; 'but': 0.36; 'too': 0.36; 'url:org': 0.36; 'received:209.85': 0.36; 'url:library': 0.36; 'subject:: ': 0.37; 'thanks': 0.37; 'thought': 0.37; 'charset:us-ascii': 0.37; 'received:209': 0.38; 'delete': 0.38; 'received:209.85.220': 0.38; 'received:192': 0.39; 'where': 0.40; 'mark': 0.40; 'url:3': 0.60; 'your': 0.60; 'header:Message-Id:1': 0.61; 'sounds': 0.76; 'removal': 0.79; 'happened.': 0.84; 'to:addr:yahoo.co.uk': 0.84 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=LbsdoDAk0hiU2ibLQgmtO0zV2vulJSTWth/rvY3sbJY=; b=TrAOCAku5TyP/GLz79dF9GyxRtiJ3UmU/Pr07RSTVET5qDv3qMdmjbLLE5HG+zsunS AA5O052qxImRAGkF+/voSTKT7zLezdQYHzkgIHf3eJVNgV0axQjCQn0uDJ5wEmOQDL1C cVS5SbG5DmQLPC0KtwGRnmtvXRXx/KZwchAw8CdWjyf2oFPfMSVfJCL05xIhJoaEbeTj 2o9bkibaX1DYGCJqFq3oIKMwjJVC1lVwCvElI/iMwQmFU8p8x0+7uUio2as2N9KGtTb7 DqKLeR9USwTCltlfc6le1uVyHzkwoXZbNmKftij6uP234HrFfto0zUYaQFPCBFmB3LeH X3Ug== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=LbsdoDAk0hiU2ibLQgmtO0zV2vulJSTWth/rvY3sbJY=; b=QRhNkFEXN3G3SgCXBboJqrnHRJ5bF0tLbtRDGWmHd8wmsCUkM6eq+ZT4Y943/lcjEm GTZdGdikwjahkxlzRC3Y9sLt3zBhcvBQUBRv+M0QTSXFrDnCiJ86E9Q7azSFFZVVa90w +Tf4xtVNw8qmuJFnaa6MpSYrHMlqThDSEHCP46oiIl+qaokMYxt5WR0UIKtMnip37xue nfgnpXp/WKLbcyQr0WttYMw1IchcY8ZDZ4ViKYIX8LUg/q+1p/gQ7rzYNNVfsYH3nSHW 4VlOjFMy5EToYYMX0aVV+F5VFETHXZhc7DQrz35nxTYKvOGNi5GUmHTdQxqOUX45o6Wb RjiA== X-Gm-Message-State: AG10YOQEEYDuKrUcbJZDN8YZHCLwKWjMC9sjkyiQ0+588gWlInMadbR5QJs5DHOJM0AUbg== X-Received: by 10.55.79.86 with SMTP id d83mr45742227qkb.22.1455064880779; Tue, 09 Feb 2016 16:41:20 -0800 (PST) In-Reply-To: X-Mailer: Apple Mail (2.1510) X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.21rc2 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:102740 On Feb 9, 2016, at 9:27 AM, Mark Lawrence = wrote: > On 09/02/2016 11:44, Cem Karan wrote: >>=20 >> On Feb 9, 2016, at 4:40 AM, Mark Lawrence = wrote: >>=20 >>> On 09/02/2016 04:25, Cem Karan wrote: >>>>=20 >>>> No problem, that's what I thought happened. And you're right, I'm = looking for a priority queue (not the only reason to use a heap, but a = pretty important reason!) >>>>=20 >>>=20 >>> I'm assuming I've missed the explanation, so what is the problem = again with = https://docs.python.org/3/library/queue.html#queue.PriorityQueue or even = https://docs.python.org/3/library/asyncio-queue.html#asyncio.PriorityQueue= ? >>=20 >> Efficiently changing the the priority of items already in the = queue/deleting items in the queue (not the first item). This comes up a = LOT in event-based simulators where it's easier to tentatively add an = event knowing that you might need to delete it or change it later. >>=20 >> Thanks, >> Cem Karan >>=20 >=20 > Thanks for that, but from the sounds of it sooner you than me :) Eh, its not too bad once you figure out how to do it. It's easier in C = though; you can use pointer tricks that let you find the element in = constant time, and then removal will involve figuring out how to fix up = your heap after you've removed the element. Thanks, Cem Karan=