On Sep 29, 2006, at 5:43 AM, moritz Hilger wrote:
hi, what happend to the binary-heap implementation in the bgl?
It's still there, called "mutable_queue".
as i can tell from older posts on the mailinglist there used to be one which was replaced by the relaxed-heap-implementation for performance reasons. nevertheless afaik the theoretical advantage of fibonacci heaps (and, probably, the relaxed heap) does not hold for some real-world problems. any chance of re-integrating alternative heap-structures for comparison reasons?
The relaxed heap has the same theoretical advantages as a Fibonacci heap, but the relaxed heap typically performs better in practice. The code to use the binary heap is still in the source files, under the control of a #define. The best way to approach this is probably to determine if there is really a tradeoff and where it occurs; if it's important, then we can parameterize the BGL algorithms on the queue type. Doug