Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min

[Junio C Hamano <gitster@pobox.com>]

René Scharfe <l.s.r@web.de> writes:

> I think I mostly understand it now: cascade is better in prio_queue_get()
> because the sift-down item is from the bottom and will likely end up back
> at the bottom, just of a different branch of the heap.  Thus a sift-down
> costs 3 compares times the number of levels, while a cascade costs just
> 2 compares times the number of levels and there is likely little to no
> need to sift it back up.
>
> For prio_queue_replace() we sift down a random item, though; we don't
> know where it will end up.  If it belongs at the very top then sift-down
> just needs 3 compares, while cascade needs 2 compares times the number
> of levels to bring the hole down and the same to bring the item up.

An excellent observation, showing clear and analytic mind.  This is
one of the reasons why I love reading review messages from you (and
also explanation in the proposed commit log messages in your
patches).

Thanks.