Re: Heap Implementation

Path	csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From	Cem Karan <cfkaran2@gmail.com>
Newsgroups	comp.lang.python
Subject	Re: Heap Implementation
Date	Mon, 8 Feb 2016 23:25:42 -0500
Lines	54
Message-ID	<mailman.118.1454991952.2317.python-list@python.org> (permalink)
References	<56AD3D83.2050308@mail.de> <7C522D08-9D73-48D2-A71D-F1D1D34C02A5@gmail.com> <CACs7g=Cu=tGhU3TtBa0cYr46WP7kOHWyxz2TiHXCuiSLqb4P7A@mail.gmail.com> <185DAEA4-8728-4792-A3B7-7F6AC5A7F876@gmail.com> <CACs7g=APHr+DbmZaGz7P3RaRUGDYPqH+eniVTFenppPXXinOvQ@mail.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	<cfkaran2@gmail.com>
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	<CACs7g=APHr+DbmZaGz7P3RaRUGDYPqH+eniVTFenppPXXinOvQ@mail.gmail.com>
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 <python-list.python.org>
List-Unsubscribe	<https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Xref	csiph.com comp.lang.python:102703

Show key headers only | View raw

On Feb 8, 2016, at 10:12 PM, srinivas devaki <mr.eightnoteight@gmail.com> wrote:

> 
> On Feb 8, 2016 5:17 PM, "Cem Karan" <cfkaran2@gmail.com> wrote:
> >
> > On Feb 7, 2016, at 10:15 PM, srinivas devaki <mr.eightnoteight@gmail.com> wrote:
> > > On Feb 8, 2016 7:07 AM, "Cem Karan" <cfkaran2@gmail.com> 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.
> 
> oh okay, I'm way too off.
> 
> what you are asking for is a Priority Queue like feature.
> 
> but the emphasis is on providing extra features to heap data structure.
> 
> and xheap doesn't support having duplicate items.
> 
> 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.
> 
> 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

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: Heap Implementation Cem Karan <cfkaran2@gmail.com> - 2016-02-08 23:25 -0500

csiph-web