Why does the Python heapq _siftup(...) call _siftdown(...) at the end?

Question

The code for_siftup at github - python/cpython/Lib/heapq.py has a final call to _siftdown:

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)

It seems like the logic in _siftup(...) is enough to place the newitem in the correct position maintaining the heap invariant? Why is a call to _siftdown() required?

Answer 1

This is the consequence of a particular choice the authors made in the algorithm.

More common is an algorithm where this final _siftdown() is not necessary, but then the loop must stop when newitem < heap[childpos], after which pos will be a valid spot for newitem and no more sifting is needed.

In this version however, the loop continues until a leaf is found, and newitem is placed at a leaf spot. This may not be a valid spot for newitem, so the extra call is needed to go back up to a valid spot.

In the comment block that precedes this function, the authors have explained why they made this choice, which at first seems to be less efficient, but in practice turns out to result in fewer comparisons:

We could break out of the loop as soon as we find a pos where newitem <= both its children, but turns out that's not a good idea, and despite that many books write the algorithm that way. During a heap pop, the last array element is sifted in, and that tends to be large, so that comparing it against values starting from the root usually doesn't pay (= usually doesn't get us out of the loop early). See Knuth, Volume 3, where this is explained and quantified in an exercise.

See also Wikipedia - bottom-up heapsort:

The change improves the linear-time heap-building phase somewhat, but is more significant in the second phase. Like ordinary heapsort, each iteration of the second phase extracts the top of the heap, a[0], and fills the gap it leaves with a[end], then sifts this latter element down the heap. But this element comes from the lowest level of the heap, meaning it is one of the [greatest]^* elements in the heap, so the sift-down will likely take many steps to move it back down. In ordinary heapsort, each step of the sift-down requires two comparisons, to find the [maximum]^* of three elements: the new node and its two children.

---

_{^* The article has "smallest" and "minimum" since it discusses a max-heap, not a min-heap as is what heapq provides.}

It is a pitty that Wikipedia discusses this in the context of heapsort, since it applies to heap interactions even when the heap does not serve a heapsort process.