On Wed, 8 Jul 2026 at 13:55, René Scharfe [off-list ref] wrote:

I meant that I didn't find this optimization in other priority queue
implementations or papers, but admittedly I didn't do an exhaustive
search.  Given it's benefits I would have expected to find prior art
on it pretty easily, though.

Aha! Got it, I misunderstood you first.
It's actually described here[1]:

Bottom-up heapsort conceptually replaces the root with a value of −∞
and sifts it down using only one comparison per level
(since no child can possibly be less than −∞)
until the leaves are reached,
then replaces the −∞ with the correct value and sifts it up
(again, using one comparison per level) until the correct position
is found.

It's for heapsort, not an interactive heap, but the algorithm
still matches.

Also, your idea to split out sift up/down into helper functions did
work, and was quite clean - will share patch shortly once I have
cleaned up the commits and benchmark data.

Thanks again,
Kristofer

[1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort