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@2ndquadrant.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