classification
Title: Possible name inversion in heapq implementation
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.8
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: Nosy List: Yomguithereal, rhettinger
Priority: normal Keywords:

Created on 2018-03-19 13:19 by Yomguithereal, last changed 2018-03-19 15:19 by rhettinger. This issue is now closed.

Messages (2)
msg314093 - (view) Author: Yomguithereal (Yomguithereal) Date: 2018-03-19 13:19
Hello Python team,

I might be hallucinating but I am under the impression that the `heapq` module uses reverse naming.

What I mean is that it seems to me that the _siftup method should actually be named _siftdown and, the other way around, _siftdown should be named _siftup.

This has absolutely no practical consequence since the module works as it should but I am a bit confused since I don't know if the module got naming wrong or if it followed another canonical naming I don't know about.

I am willing to open a PR to fix this if the named reverasl was to be confirmed.

Good day to you.
msg314097 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-03-19 15:19
There isn't universal agreement on whether it should be sift up or sift down.  One point of view for sift down is that the datum is moving downward.  The other point of view is that the datum is stationary which the rest of the heap moves downward (like sifting a ring out of flour).  Different sources make different choices in this regard. 


"There is some confusion in the literature on the naming of the siftup/down routines. presented above. The routine named siftdown here is called siftdown in [1], siftup. in [3], trickledown in [4] and heapify in [5]." -- www.diku.dk/~jyrki/PE-lab/Jesper/heaplab/survey.ps.gz
History
Date User Action Args
2018-03-19 15:19:54rhettingersetstatus: open -> closed

nosy: + rhettinger
messages: + msg314097

resolution: not a bug
stage: resolved
2018-03-19 13:19:15Yomguitherealcreate