From: Kristofer Karlsson Date: Wed, 08 Jul 2026 12:44:06 GMT Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min Message-ID: In-Reply-To: <15fa1b16-b911-47b1-a843-400e320d7e4f@web.de> On Wed, 8 Jul 2026 at 13:55, René Scharfe 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