3

From the definition of binary heap in Wikipedia, sift-up is also called up-heap operation, and sift-down is called down-heap.

So in heap (complete binary tree), up means from leaf to root, and down means from root to leaf.

But in python, it seems just opposite. I'm confused by meaning of siftup and siftdown, and misused when my first time.

Here is the python version implementation of _siftdown and _siftup in heapq:

# 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
# is the index of a leaf with a possibly out-of-order value.  Restore the
# heap invariant.
def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

Why opposite in python? I have confirmed in wiki and several other articles. Is there anything I missing or misunderstanding?

Thanks for reading, I really appreciate it to help me out. : )

recnac
  • 3,744
  • 6
  • 24
  • 46
  • 1
    You are not suppose to use either of those directly. They are internal to the heapq module as the underscore in their name denotes. – Dan D. Mar 27 '19 at 10:59

1 Answers1

6

Looking at the references on the Wikipedia page, I spotted this:

Note that this paper uses Floyd's original terminology "siftup" for what is now called sifting down.

It would seem that different authors have different references for what is "up" and "down".

But, as @Dan D writes in a comment, you are not supposed to be using those functions anyway.

Ture Pålsson
  • 6,088
  • 2
  • 12
  • 15
  • thanks both of you @Dan D. I try to avoid use them either, and that is my another question, [how to avoid using _siftup and _siftdown when one element is out-of-order in heap](https://stackoverflow.com/questions/55373969/how-to-avoid-using-siftup-or-siftdown-in-heapq) – recnac Mar 27 '19 at 11:12