Re: Reduce one comparison in binaryheap's sift down

On Mon, Oct 28, 2024 at 11:22 AM cca5507 <cca5507(at)qq(dot)com> wrote:
> I think we can reduce one comparison in binaryheap's sift down, right?
>
> Here is a patch to fix it.

Hmm, so at present we compare the parent to the left child and to the
right child. If it's smaller than neither, everything is OK. If it's
smaller than one, we swap it with that one. If it's smaller than both,
we compare the left and right child with each other and swap the
parent with the larger of the two. Hence, if a node has 2 children, we
always do 2 comparisons, and we sometimes do 3 comparisons.

With the patch, we first compare the two children to each other, and
then compare the larger one to the parent. If the parent is smaller
than the larger child, we swap them. Hene, if a node has 2 children,
we always do 2 comparisons.

Unless I'm missing something, that does seem significantly better.

--
Robert Haas
EDB: http://www.enterprisedb.com