Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jul 8, 2026, 12:44 UTC
- Message-ID
- <CAL71e4NKcCBs-UjF3ZxOGrTbT_TUAumZV_G2PAfyf4JgzCm+Cg@mail.gmail.com>
- In-Reply-To
- <15fa1b16-b911-47b1-a843-400e320d7e4f@web.de>
On Wed, 8 Jul 2026 at 13:55, René Scharfe <l.s.r@web.de> wrote:
Show 5 quoted lines
> > 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]:
Show 7 quoted lines
> 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