Re: [PATCH 2/3] prio-queue: add prio_queue_replace()

From: Jeff King <peff@peff.net>
Date: Jul 16, 2025, 05:09 UTC
Message-ID: <20250716050933.GC1396022@coredump.intra.peff.net>
In-Reply-To: <cbabed69-b44a-4920-9a56-e81b404be2de@web.de>

On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote:

Show 6 quoted lines

> 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.

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)?

-Peff