Re: _siftup and _siftdown implementation

Path	csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From	srinivas devaki <mr.eightnoteight@gmail.com>
Newsgroups	comp.lang.python
Subject	Re: _siftup and _siftdown implementation
Date	Fri, 5 Feb 2016 06:56:12 +0530
Lines	41
Message-ID	<mailman.75.1454635582.30993.python-list@python.org> (permalink)
References	<mailman.72.1454619005.30993.python-list@python.org> <56b3e902$0$1613$c3e8da3$5496439d@news.astraweb.com>
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8
X-Trace	news.uni-berlin.de SL5ln/gaQxGI+cC2rcr+ZAM6CWOZLHADuRuIagrKidfA==
Return-Path	<mr.eightnoteight@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.007
X-Spam-Evidence	'H': 0.99; 'S': 0.00; 'received:209.85.223': 0.03; 'root': 0.04; 'library?': 0.09; 'modules.': 0.09; 'sub': 0.09; 'python': 0.10; '+91': 0.15; '2016': 0.16; 'code?': 0.16; 'fashion,': 0.16; 'heap': 0.16; 'heapq': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'wrote:': 0.16; 'element': 0.18; '>': 0.18; 'student': 0.20; 'junior': 0.22; 'pos': 0.22; 'subject:skip:i 10': 0.22; 'am,': 0.23; 'feb': 0.23; 'implemented': 0.24; 'header:In-Reply-To:1': 0.24; 'wondering': 0.25; 'fri,': 0.27; 'question': 0.27; 'message- id:@mail.gmail.com': 0.27; 'module.': 0.27; 'function': 0.28; 'idea': 0.28; "i'm": 0.30; 'that.': 0.30; 'code': 0.30; 'compared': 0.30; 'somebody': 0.30; 'posting': 0.32; 'programming,': 0.33; 'received:google.com': 0.35; 'so,': 0.35; 'level': 0.35; 'but': 0.36; 'received:209.85': 0.36; 'indian': 0.36; 'modules': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'thought': 0.37; 'list.': 0.37; 'received:209': 0.38; 'mailing': 0.38; 'why': 0.39; 'sure': 0.39; "didn't": 0.39; 'to:addr:python.org': 0.40; 'where': 0.40; 'some': 0.40; 'your': 0.60; 'competitive': 0.61; 'hope': 0.61; 'school': 0.62; 'bring': 0.62; 'us.': 0.62; 'cut': 0.67; 'obvious': 0.76; '(3rd': 0.84; "else's": 0.84; 'ph:': 0.84
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=s/5WShzsNalX2XYz8ObToX8Ho0MFjPXzsrZ61r9uM9c=; b=dy8ywviS8ueE2rDVZPHfwhZm+iIW/DkrSEVQpufPYBJWylTzn54NAMjsVv8q/tYMdX clpLEj+TWfNGV4ekfoOYX890JT/9+Qwh8PQrHP34FcQHC+3Wk+ierElKCdz0rjPTKjqO YMel44PZcwjAt5wK5VEGObt802Ic9wdjsbAiwENRSpsidN4OB7wFasc0ts0wVKHsGRJ+ L4MKm2hCVVXVwP2MmUMjalEnarHrIvtUtMZH6KfHbpQcv3xThIjBT0ssb5Yk92UveFrJ bGe6pF7PdvWPekMAlB2Aua20YP5pknbCiCoJoXV0HXDkJlmbTKq0rKk1gG013PbgN/Bg nbyg==
X-Google-DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:content-type; bh=s/5WShzsNalX2XYz8ObToX8Ho0MFjPXzsrZ61r9uM9c=; b=hiDGKQ2o+M+JlkExMdBNM0znQpAFNOvJ17sJcj5zUcQ8S2cIKC8FECt8KQd6/gMu+D yAsaBNRA2kyWoGSDLXK3xTAYeOMmMLrALYT6GG6/1ivcv3xZQWo1po2quyRxW5fBDEmf jXWkYeqOdCn/zXP4mJKJ25+q8i62sNrdoVz+ya46vTOlVkosD1WU8WIlhXTUCZwj22L1 tQ0gaW5wGFCkuFDRu1wLSuzeAcHJQ9UIXxnb60jI2H5AX83J5ssfUJmzcSv/aKMA6D/N Kux4WeFa5VuZyzDtrnBsk+W+r3eedBzCj/BQKB+It3mDt1WzsG5FWI+xjEJqGGSfls0C Vxag==
X-Gm-Message-State	AG10YOSp2JXOnf7rvmdC6dBMhCGNp9P9zREw+1sb7AiXcrlgwWpitVVA+RIn77N4fiuRDZbFG6bPbi02PLD0wQ==
X-Received	by 10.107.18.199 with SMTP id 68mr11861642ios.130.1454635573080; Thu, 04 Feb 2016 17:26:13 -0800 (PST)
In-Reply-To	<56b3e902$0$1613$c3e8da3$5496439d@news.astraweb.com>
X-Content-Filtered-By	Mailman/MimeDel 2.1.21rc1
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.21rc1
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:102510

Show key headers only | View raw

On Feb 5, 2016 5:45 AM, "Steven D'Aprano" <steve@pearwood.info> wrote:
>
> On Fri, 5 Feb 2016 07:50 am, srinivas devaki wrote:
>
> > _siftdown function breaks out of the loop when the current pos has a
valid
> > parent.
> >
> > but _siftup function is not implemented in that fashion, if a valid
> > subheap is given to the _siftup, it will bring down the root of sub heap
> > and then again bring it up to its original place.

as I come to think of it again, it is not subheap, it actually heap cut at
some level hope you get the idea from the usage of _siftup. so even though
the `pos` children are valid the _siftup brings down the new element (i.e
the element which is at first at `pos`) upto its leaf level and then again
it is brought up by using _siftdown. why do the redundant work when it can
simply breakout?

> >
> > I was wondering why it is so, is it just to make the code look simple???
>
> Hi Srinivas,
>
> I'm sure that your question is obvious to you, but it's not obvious to us.
> Where are _siftup and _siftdown defined? Are they in your code? Somebody
> else's code? A library? Which library? What do they do? Where are they
> from?

_siftup and _siftdown are functions from python standard heapq module.

PS: I do competitive programming, I use these modules every couple of days
when compared to other modules. so didn't give much thought when posting to
the mailing list. sorry for that.

Regards
Srinivas Devaki
Junior (3rd yr) student at Indian School of Mines,(IIT Dhanbad)
Computer Science and Engineering Department
ph: +91 9491 383 249
telegram_id: @eightnoteight

Thread

_siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 02:20 +0530
  Re: _siftup and _siftdown implementation Steven D'Aprano <steve@pearwood.info> - 2016-02-05 11:12 +1100
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 01:21 +0100
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 06:56 +0530
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 15:42 +0100
    Re: _siftup and _siftdown implementation Bernardo Sulzbach <mafagafogigante@gmail.com> - 2016-02-05 12:48 -0200
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 15:55 +0100
    Re: _siftup and _siftdown implementation Bernardo Sulzbach <mafagafogigante@gmail.com> - 2016-02-05 12:59 -0200
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 21:15 +0530
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 17:27 +0100
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 17:35 +0100
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 23:12 +0530
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-06 20:16 +0530

csiph-web