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.
That does show that the algorithms are related, though, and maybe a proposal (like this one) ought to consider them together.
–Arthur,
scope-creeping