On 7/16/25 7:09 AM, Jeff King wrote: > On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote: > >> Add a function to replace the top element of the queue that basically >> does the same as prio_queue_get() followed by prio_queue_put(), but >> without the work by prio_queue_get() to rebalance the heap. It can be >> used to optimize loops that get one element and then immediately add >> another one. That's common e.g., with commit history traversal, where >> we get out a commit and then put in its parents. > > Hmm. But surely we still need to rebalance the heap after adding an > element? And indeed, we still call the new sift_down_root() function. Yes. > But I guess we are getting away without the "bubble up" operation that > put would do? So we are doing half as much work (but still big-O the > same)? Yes. I thought about building this optimization into prio_queue_get(), but that would require prio_queue_peek() and prio_queue_put() to be adjusted as well and all prio_queue users would have to be either made aware of the not-fully-heapified state, or prevented from accessing prio_queue properties like .nr and .array. Adding a new function seemed like the simplest and safest way for now. René
