On Wed, Jan 21, 2026 at 4:38 PM Ell <ell.ell.se_at_[hidden]> wrote:

> There's an even more primitive operation here, of replacing the top
> element with a new value (that is, a combined pop+push). This is common
> when using a fixed-size heap, and is more efficient that doing the pop and
> push separately, since the last step of pop_heap() is already a push (of
> the previous tail). Python has it as heapq.heapreplace() <
> https://docs.python.org/3/library/heapq.html#heapq.heapreplace>.


Yep — I call that `pq.replace_top(value)`, `pq.reemplace_top(args...)` —
see my blog post from 2018
<https://quuxplusone.github.io/blog/2018/04/27/pq-replace-top/> — but I
wasn't going to open that can of worms. ;) I thought it was orthogonal.


> If we had replace_heap(), then a discarding/returning pop would simply be
> `replace_heap (first, last - 1, iter_move (last - 1))`.
>

I question that.
`pq.replace_top(x)` doesn't have any special knowledge about the value of
x, but `replace_heap(first, last - 1, iter_move(last - 1))` *does* have
special knowledge: it knows that the incoming element is "leaf-sized,"
which means it's going to sift basically all the way to the bottom. So it
does Floyd's sift-down, the "heapsort with bounce" that I linked in my
first message in this thread. It's not immediately obvious to me that
"heapsort with bounce" is the right thing to do inside the general-purpose
`pq.replace_top(x)`, which for all we know is being used to *decrement* the
top element, or something.

That does show that the algorithms are related, though, and *maybe* a
proposal (like this one) ought to consider them together.

–Arthur,
scope-creeping