Re: [boost] [heap] A performance test and some questions

Subject: Re: [boost] [heap] A performance test and some questions
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-06 12:02:07

> I have now read (and tried to understand) the similar question from Andrew Sutton with respect to Dijkstra's SP:
> <http://lists.boost.org/Archives/boost/2011/06/182381.php>
>
> (On a slightly unrelated note, I first also used his way to call "update", but that totally killed the performance (and compare count) of fibonacci_heap. I would suggest to remove this form of "update" at least from fibonacci_heap, and require calling "increase" or "decrease" when you have modified the priority "manually".)

That's only a viable solution if you have some a priori knowledge
about which "direction" the value has changed with respect to the
comparison operator. If you have an expression like this:

x' = x + y;

where x is the previous key and x' the new key--a possible
implementation of edge relaxation. You still have to compare x and x'
to determine which direction the change was in. Minimally, you'd have
to check y to determine if it was less than 0, assuming the types of
x, x', and y are numeric.

Removing the update() method makes the user work harder. Increase and
decrease are nice when you know that you can optimize.

Andrew