Re: [Boost-users] [BGL] binary heap

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-09-29 09:33:57

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