Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Cem Karan Newsgroups: comp.lang.python Subject: Re: Heap Implementation Date: Mon, 8 Feb 2016 23:25:42 -0500 Lines: 54 Message-ID: References: <56AD3D83.2050308@mail.de> <7C522D08-9D73-48D2-A71D-F1D1D34C02A5@gmail.com> <185DAEA4-8728-4792-A3B7-7F6AC5A7F876@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 iafLwKn5Ivv5E9bght6DFwes6QGrSt2W5f8OJvrx35yA== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.004 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'feature.': 0.07; 'cc:addr :python-list': 0.09; 'dict': 0.09; 'subclass': 0.09; 'times,': 0.13; 'argument': 0.15; '10:15': 0.16; '2016': 0.16; '7:07': 0.16; 'distinct': 0.16; 'heap': 0.16; 'heap,': 0.16; 'keys.': 0.16; 'pairs': 0.16; 'received:192.168.1.4': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'side.': 0.16; 'structure.': 0.16; 'wrote:': 0.16; 'duplicate': 0.18; 'library,': 0.18; '(not': 0.20; 'library': 0.20; 'cc:addr:python.org': 0.20; 'proposed': 0.20; 'cc:2**1': 0.22; 'meant': 0.22; 'am,': 0.23; 'feb': 0.23; 'insert': 0.23; 'thanks,': 0.24; 'header:In-Reply-To:1': 0.24; 'feature': 0.24; "doesn't": 0.26; 'handling': 0.27; 'separate': 0.27; 'idea': 0.28; 'directly,': 0.29; 'fast.': 0.29; 'queue': 0.29; "i'm": 0.30; 'another': 0.32; 'useful': 0.33; 'instances': 0.33; 'items.': 0.33; 'message-id:@gmail.com': 0.34; 'handle': 0.34; 'received:google.com': 0.35; 'could': 0.35; 'library.': 0.35; 'asking': 0.35; 'item': 0.35; 'but': 0.36; 'too': 0.36; 'should': 0.36; 'instead': 0.36; 'there': 0.36; 'received:209.85': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'method': 0.37; 'client': 0.37; 'thought': 0.37; 'charset:us-ascii': 0.37; 'received:209': 0.38; 'data': 0.39; 'easily': 0.39; 'received:192': 0.39; 'well.': 0.40; 'still': 0.40; 'your': 0.60; 'header:Message-Id:1': 0.61; 'provide': 0.61; 'providing': 0.62; 'different': 0.63; 'introduce': 0.79; 'client-side': 0.84; 'dict,': 0.84; 'happened.': 0.84; 'priorities,': 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=uglr49fxU8yJgP9RTNZmFkriHrq89y9UZpo12Ek71V0=; b=g9SCKBYYRpz20bStd0s51ltIcj2VTPP8VlpTuCBjxUIB0nE+V4pY1Ah2E17E5dm9TZ gjFQM+nnwc86QIigL7j7O3Hhd5fLyGL5in3Y76bkT5akB3OLcn/8eZYkRPI3L5Jrj9Yh B08W0dLIskNoyNu8FAe/WLp4jD+9xbR3Mi/TJwLML9QskNC5mWeiiGubZg/BBTsKW1nk oT2pMoxm3W1eaRzashd9jhpg18/iLlzgAa3W6JKG5bsDoV27RLzXraVejdOrigTUMM9u F9kpjnSYgjtwxk48NMlZwJE//IPt9sY7Vxuas8n+5auBIDcZ2uqOsm8HM0rXnHFPCM+J Bf8g== 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=uglr49fxU8yJgP9RTNZmFkriHrq89y9UZpo12Ek71V0=; b=NV4p4sc8qUmZUeYC0kvh+dY5NwcrxCxi0/mRxvrYvB5ckc+t46P6M4SMFMe6LSPeQY S2sDozZs6nTI1fPjU6hYNz6yt9XbKwXnqzQpzO+DG9hH/wpBWiR+77IPvKWqg4/azx3x JJpWjMgNAN5YD1JLnuUd4z9Z5zwe2TPf96yEWYGhrekxN+2IS49sz7MbhhhNM5gErT40 cKkYM8YrfEx39/V4B7US3LMyVg2zXk+UCcylkF7jfCWnbEiwwGUNBIDpC5T/DK9ZBtZy gqWKOBY34tLKviQMUyLLKANl4LX3zMvGjlD2JeikAISe+lB4V5Ews12SVmtiNlnVkWi7 2YOQ== X-Gm-Message-State: AG10YOS09T4e+pBN02Ik57iZ8MfmWUqYY7qgFadwpPn+STrnjBmK7rkox+vXokhNZ2LbNQ== X-Received: by 10.140.229.209 with SMTP id z200mr40966945qhb.40.1454991942805; Mon, 08 Feb 2016 20:25:42 -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:102703 On Feb 8, 2016, at 10:12 PM, srinivas devaki = wrote: >=20 > On Feb 8, 2016 5:17 PM, "Cem Karan" wrote: > > > > On Feb 7, 2016, at 10:15 PM, srinivas devaki = wrote: > > > On Feb 8, 2016 7:07 AM, "Cem Karan" wrote: > > > > I know that there are methods of handling this from the = client-side (tuples with unique counters come to mind), but if your = library can handle it directly, then that could be useful to others as = well. > > > > > > yeah it is a good idea to do at client side. > > > but if it should be introduced as feature into the library, = instead of tuples, we should just piggyback a single counter it to the = self._indexes dict, or better make another self._counts dict which will = be light and fast. > > > and if you think again with this method you can easily subclass = with just using self._counts dict in your subclass. but still I think = it is good to introduce it as a feature in the library. > > > > > > Regards > > > Srinivas Devaki > > > > I meant that the counter is a trick to separate different instances = of (item, priority) pairs when you're pushing in the same item multiple = times, but with different priorities. >=20 > oh okay, I'm way too off. >=20 > what you are asking for is a Priority Queue like feature. >=20 > but the emphasis is on providing extra features to heap data = structure. >=20 > and xheap doesn't support having duplicate items. >=20 > and if you want to insert same items with distinct priorities, you can = provide the priority with key argument to the xheap. what xheap doesn't = support is having same keys/priorities. > So I got confused and proposed a method to have same keys. >=20 > Regards > Srinivas Devaki 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!) Thanks, Cem Karan=