Date: Thu, 22 Jan 2026 11:44:30 +0000
On Thursday, January 22nd, 2026 at 2:15 AM, Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]> wrote:
> 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 — 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.
Right. My logic was that an arbitrary element is going to end up at the bottom on average, so a single-comparison, full sift-down is still better than a double-comparison, partial sift-down, even in a general-purpose function. But maybe the new element becoming the new root is a common enough special case to deserve special treatment. OOC, did you have something specific in mind?
>
> That does show that the algorithms are related, though, and maybe a proposal (like this one) ought to consider them together.
>
> –Arthur,
> scope-creeping
Yeah, I should have included a feature-creep warning :)
> 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 — 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.
Right. My logic was that an arbitrary element is going to end up at the bottom on average, so a single-comparison, full sift-down is still better than a double-comparison, partial sift-down, even in a general-purpose function. But maybe the new element becoming the new root is a common enough special case to deserve special treatment. OOC, did you have something specific in mind?
>
> That does show that the algorithms are related, though, and maybe a proposal (like this one) ought to consider them together.
>
> –Arthur,
> scope-creeping
Yeah, I should have included a feature-creep warning :)
Received on 2026-01-22 11:44:37