Re: [PATCH] binary heap implementation

On 2012-11-27 11:56:41 -0500, Robert Haas wrote:
> [ Sorry for the slow response on this, Thanksgiving interfered. ]
>
> On Wed, Nov 21, 2012 at 3:41 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> > One very minor nitpick I unfortunately just found now, not sure when
> > that changed:
> > binaryheap_replace_first() hardcodes the indices for the left/right node
> > of the root node. I would rather have it use (left|right)_offset(0).
>
> Hmm, yeah... but come to think of it, why do we need that special case
> at all? Why not just call sift_down on the root node and call it
> good? See the attached version, which simplifies the code
> considerably and also makes some comment adjustments per Abhijit's
> comments.

The simplification made me worry for a second but after checking it out
I realized that my fear was only based on my original version where I
did a
kv = simpleheap_remove_first(heap);
simpleheap_add(heap, kv->key, kv->value);
if there was work to be done. But Abhijit optimized that code to do less
work, so the amount of comparisons is exactly the same before/after your
simplifications. With considerably less code.

Looks ready to me.

Thanks,

Andres

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services