Re: [PATCH]: Fibheap (commented more)

[Richard Henderson <rth at redhat dot com>]

On Fri, Aug 17, 2001 at 05:18:30PM -0400, Daniel Berlin wrote:
> I indent -gnu'd it, and that's what it did to it (I had two spaces
> after the period before then).
> So i'm a bit confused.

Perhaps a bug in indent then.

> Note the compare in replace_key_data uses "<= 0" for the comparisons,
> specifically to allow delete to get the right element.

If there's something in replace_key_data that makes sure that ties
are broken by putting the changing node first, then you're right that
we don't need a neginf flag.  That's a subtlety deserving of a comment
both in delete and in replace_key though.

> Why recursively walk all the nodes? It's not going to be all that much
> faster unless you have a billion nodes (n vs n log n).

I'd bet the constant is much much lower for the walk
than the extractmin.


r~